BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Michael Walter

Michael Walter contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phmath-phmath.MPComputational ComplexityData Structures and Algorithmshep-thmath.RAmath.RTphysics.chem-phCryptography and SecurityInformation Theorymath.AGmath.ITmath.OCphysics.comp-phphysics.ins-detphysics.space-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
15works
0followers
17topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2024arXiv

Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution

Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel. Compared to classical key exchange, it has two main advantages: (i) The key is unconditionally hidden to the eyes of any attacker, and (ii) its security assumes only the existence of authenticated classical channels which, in practice, can be realized using Minicrypt assumptions, such as the existence of digital signatures. On the flip side, QKD protocols typically require multiple rounds of interactions, whereas classical key exchange can be realized with the minimal amount of two messages using public-key encryption. A long-standing open question is whether QKD requires more rounds of interaction than classical key exchange. In this work, we propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions. That is, the shared key is unconditionally hidden, provided computational assumptions hold during the protocol execution. Our result follows from a new construction of quantum public-key encryption (QPKE) whose security, much like its classical counterpart, only relies on authenticated classical channels.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Excitation dynamics in polyacene molecules on rare-gas clusters

Laser-induced fluorescence spectra and excitation lifetimes of anthracene, tetracene, and pentacene molecules attached to the surface of solid argon clusters have been measured with respect to cluster size, density of molecules and excitation density. Results are compared to previous studies on the same sample molecules attached to neon clusters. A contrasting lifetime behavior of anthracene on neon and argon clusters is discussed, and mechanisms are suggested to interpret the results. Although both neon and argon clusters are considered to be weakly interacting environments, we find that the excitation decay dynamics of the studied acenes depends significantly on the cluster material. Moreover, we find even qualitative differences regarding the dependence on the dopant density. Based on these observations, previous assignments of collective radiative and non-radiative decay mechanisms are discussed in the context of the new experimental findings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Matchgate benchmarking: Scalable benchmarking of a continuous family of many-qubit gates

We propose a method to reliably and efficiently extract the fidelity of many-qubit quantum circuits composed of continuously parametrized two-qubit gates called matchgates. This method, which we call matchgate benchmarking, relies on advanced techniques from randomized benchmarking as well as insights from the representation theory of matchgate circuits. We argue the formal correctness and scalability of the protocol, and moreover deploy it to estimate the performance of matchgate circuits generated by two-qubit XY spin interactions on a quantum processor.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Multipartite Entanglement in Stabilizer Tensor Networks

Despite the fundamental importance of quantum entanglement in many-body systems, our understanding is mostly limited to bipartite situations. Indeed, even defining appropriate notions of multipartite entanglement is a significant challenge for general quantum systems. In this work, we initiate the study of multipartite entanglement in a rich, yet tractable class of quantum states called stabilizer tensor networks. We demonstrate that, for generic stabilizer tensor networks, the geometry of the tensor network informs the multipartite entanglement structure of the state. In particular, we show that the average number of Greenberger-Horne-Zeilinger (GHZ) triples that can be extracted from a stabilizer tensor network is small, implying that tripartite entanglement is scarce. This, in turn, restricts the higher-partite entanglement structure of the states. Recent research in quantum gravity found that stabilizer tensor networks reproduce important structural features of the AdS/CFT correspondence, including the Ryu-Takayanagi formula for the entanglement entropy and certain quantum error correction properties. Our results imply a new operational interpretation of the monogamy of the Ryu-Takayanagi mutual information and an entropic diagnostic for higher-partite entanglement. Our technical contributions include a spin model for evaluating the average GHZ content of stabilizer tensor networks, as well as a novel formula for the third moment of random stabilizer states, which we expect to find further applications in quantum information.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quantum circuit approximations and entanglement renormalization for the Dirac field in 1+1 dimensions

The multiscale entanglement renormalization ansatz describes quantum many-body states by a hierarchical entanglement structure organized by length scale. Numerically, it has been demonstrated to capture critical lattice models and the data of the corresponding conformal field theories with high accuracy. However, a rigorous understanding of its success and precise relation to the continuum is still lacking. To address this challenge, we provide an explicit construction of entanglement-renormalization quantum circuits that rigorously approximate correlation functions of the massless Dirac conformal field theory. We directly target the continuum theory: discreteness is introduced by our choice of how to probe the system, not by any underlying short-distance lattice regulator. To achieve this, we use multiresolution analysis from wavelet theory to obtain an approximation scheme and to implement entanglement renormalization in a natural way. This could be a starting point for constructing quantum circuit approximations for more general conformal field theories.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Quantum Multiparty Packing Lemma and the Relay Channel

Optimally encoding classical information in a quantum system is one of the oldest and most fundamental challenges of quantum information theory. Holevo's bound places a hard upper limit on such encodings, while the Holevo-Schumacher-Westmoreland (HSW) theorem addresses the question of how many classical messages can be "packed" into a given quantum system. In this article, we use Sen's recent quantum joint typicality results to prove a one-shot multiparty quantum packing lemma generalizing the HSW theorem. The lemma is designed to be easily applicable in many network communication scenarios. As an illustration, we use it to straightforwardly obtain quantum generalizations of well-known classical coding schemes for the relay channel: multihop, coherent multihop, decode-forward, and partial decode-forward. We provide both finite blocklength and asymptotic results, the latter matching existing classical formulas. Given the key role of the classical packing lemma in network information theory, our packing lemma should help open the field to direct quantum generalization.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hyperpfaffians and Geometric Complexity Theory

The hyperpfaffian polynomial was introduced by Barvinok in 1995 as a natural generalization of the well-known Pfaffian polynomial to higher order tensors. We prove that the hyperpfaffian is the unique smallest degree SL-invariant on the space of higher order tensors. We then study the hyperpfaffian's computational complexity and prove that it is VNP-complete. This disproves a conjecture of Mulmuley in geometric complexity theory about the computational complexity of invariant rings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Interior-point methods for unconstrained geometric programming and scaling problems

We provide a condition-based analysis of two interior-point methods for unconstrained geometric programs, a class of convex programs that arise naturally in applications including matrix scaling, matrix balancing, and entropy maximization. Our condition numbers are natural geometric quantities associated with the Newton polytope of the geometric program, and lead to diameter bounds on approximate minimizers. We also provide effective bounds on the condition numbers both in general and under combinatorial assumptions on the Newton polytope. In this way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing. Recently, there has been much work on algorithms for certain optimization problems on Lie groups, known as capacity and scaling problems. For commutative groups, these problems reduce to unconstrained geometric programs, which serves as a particular source of motivation for our work.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reliable computational prediction of supramolecular ordering of complex molecules under electrochemical conditions

We propose a computationally lean, two-stage approach that reliably predicts self-assembly behavior of complex charged molecules on a metallic surfaces under electrochemical conditions. Stage one uses ab initio simulations to provide reference data for the energies (evaluated for archetypical configurations) to fit the parameters of a conceptually much simpler and computationally less expensive model of the molecules: classical, spherical particles, representing the respective atomic entities, a soft but perfectly conductive wall potential represents the metallic surface. Stage two feeds the energies that emerge from this classical model into highly efficient and reliable optimization techniques to identify via energy minimization the ordered ground state configurations of the molecules. We demonstrate the power of our approach by successfully reproducing, on a semi-quantitative level, the intricate supramolecular ordering observed experimentally for PQP$^+$ and ClO$_4^-$ molecules at an Au(111)-electrolyte interface, including the formation of open-porous, self-hosts--guest, and stratified bilayer phases as a function of the electric field at the solid--liquid interface. We also discuss the role of the perchlorate ions in the self-assembly process, whose positions could not be identified in the related experimental investigations.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings

We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized such encodings for invariant rings of $\SL_n(\C)$-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions). We develop a general framework, denoted \emph{algebraic circuit search problems}, that captures many important problems in algebraic complexity and computational invariant theory. This framework encompasses various proof systems in proof complexity and some of the central problems in invariant theory as exposed by the Geometric Complexity Theory (GCT) program, including the aforementioned problem of computing succinct encodings for generators for invariant rings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The mini-neutron monitor: A new approach in neutron monitor design

The near-Earth cosmic ray flux has been monitored for more than 70 years by a network of ground-based neutron monitors (NMs). With the ever-increasing importance of quantifying the radiation risk and effects of cosmic rays for, e.g., air and space-travel, it is essential to continue operating the existing NM stations, while expanding this crucial network. In this paper, we discuss a smaller and cost-effective version of the traditional NM, the mini-NM. These monitors can be deployed with ease, even to extremely remote locations, where they operate in a semi-autonomous fashion. We believe that the mini-NM, therefore, offers the opportunity to increase the sensitivity and expand the coverage of the existing NM network, making this network more suitable to near-real-time monitoring for space weather applications. In this paper, we present the technical details of the mini-NM's design and operation, and present a summary of the initial tests and science results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Witnessing Entanglement in Experiments with Correlated Noise

The purpose of an entanglement witness experiment is to certify the creation of an entangled state from a finite number of trials. The statistical confidence of such an experiment is typically expressed as the number of observed standard deviations of witness violations. This method implicitly assumes that the noise is well-behaved so that the central limit theorem applies. In this work, we propose two methods to analyze witness experiments where the states can be subject to arbitrarily correlated noise. Our first method is a rejection experiment, in which we certify the creation of entanglement by rejecting the hypothesis that the experiment can only produce separable states. We quantify the statistical confidence by a p-value, which can be interpreted as the likelihood that the observed data is consistent with the hypothesis that only separable states can be produced. Hence a small p-value implies large confidence in the witnessed entanglement. The method applies to general witness experiments and can also be used to witness genuine multipartite entanglement. Our second method is an estimation experiment, in which we estimate and construct confidence intervals for the average witness value. This confidence interval is statistically rigorous in the presence of correlated noise. The method applies to general estimation problems, including fidelity estimation. To account for systematic measurement and random setting generation errors, our model takes into account device imperfections and we show how this affects both methods of statistical analysis. Finally, we illustrate the use of our methods with detailed examples based on a simulation of NV centers.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Asymptotic performance of port-based teleportation

Quantum teleportation is one of the fundamental building blocks of quantum Shannon theory. While ordinary teleportation is simple and efficient, port-based teleportation (PBT) enables applications such as universal programmable quantum processors, instantaneous non-local quantum computation and attacks on position-based quantum cryptography. In this work, we determine the fundamental limit on the performance of PBT: for arbitrary fixed input dimension and a large number $N$ of ports, the error of the optimal protocol is proportional to the inverse square of $N$. We prove this by deriving an achievability bound, obtained by relating the corresponding optimization problem to the lowest Dirichlet eigenvalue of the Laplacian on the ordered simplex. We also give an improved converse bound of matching order in the number of ports. In addition, we determine the leading-order asymptotics of PBT variants defined in terms of maximally entangled resource states. The proofs of these results rely on connecting recently-derived representation-theoretic formulas to random matrix theory. Along the way, we refine a convergence result for the fluctuations of the Schur-Weyl distribution by Johansson, which might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Efficient algorithms for tensor scaling, quantum marginals and moment polytopes

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory

Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).

0 citations0 reviewsNo code linkedOpen access