The Quantum Formalization Drive

Large-scale quantum computers will not run on bare physical qubits. Every proposal in the fault-tolerance literature encodes one logical qubit into many physical qubits and corrects errors faster than they accumulate. The Steane code, seven physical qubits per logical qubit, is a standard code on which the Hadamard, Pauli, phase and controlled-NOT gates all…

Bell nonlocality can be formulated in terms of a resource theory with local-hidden variable models as resourceless objects. Two such theories are known, one built upon local operations assisted by shared randomness (LOSRs) and the other one allowing, in addition, for prior-to-input classical communication. We show that prior communication, although unable…

Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of $0.526$ on every graph with nonnegative rational edge weights.

Quantum Max-Cut asks for the largest eigenvalue of $H_G=\sum_{i<j}w_{ij}(I-\mathrm{SWAP}_{ij})$ on a graph with nonnegative rational weights. This mission formalizes the classical numerical $0.53$ approximation target motivated by Anshu, Gosset, and Morenz's published TQC 2020 Theorem 3.

A qubit that sits in the environment of a physical device loses its information through coupling to that environment. Chapter 15 of Dave Bacon's thesis (arXiv:quant-ph/0305025) sorts decoherence by its effect on the system's energy: a process can lower the energy (cooling), raise it (heating), or leave it unchanged (non-dissipative). Heating processes need…

Bit commitment is a two-party primitive: Alice fixes a bit $b$ that Bob cannot learn (the commitment is concealing), and later reveals it in a way that prevents her from changing her mind (the commitment is binding). Many cryptographic tasks, among them oblivious transfer and secure two-party computation, are built on it. In the early 1990s it was widely…

We propose a family of exactly solvable toy models for the AdS/CFT correspondence based on a novel construction of quantum error-correcting codes with a tensor network structure. Our building block is a special type of tensor with maximal entanglement along any bipartition, which gives rise to an isometry from the bulk Hilbert space to the boundary Hilbert…

Variational quantum circuits are used in quantum machine learning and variational quantum simulation tasks. Designing good variational circuits or predicting how well they perform for given learning or optimization tasks is still unclear. Here we discuss these problems, analyzing variational quantum circuits using the theory of neural tangent kernels. We…

Quantum key distribution is widely thought to offer unconditional security in communication between two users. Unfortunately, a widely accepted proof of its security in the presence of source, device and channel noises has been missing. This long-standing problem is solved here by showing that, given fault-tolerant quantum computers, quantum key…

The partition algebras are algebras of diagrams (which contain the group algebra of the symmetric group and the Brauer algebra) such that the multiplication is given by a combinatorial rule and such that the structure constants of the algebra depend polynomially on a parameter. This is a survey paper which proves the primary results in the theory of…

The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via block encoding circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and…

Bit commitment is a two-phase protocol between Alice and Bob. In the commit phase Alice fixes a bit $b$ and gives Bob some evidence of it; in the opening phase she reveals $b$ and Bob checks it against the evidence. The protocol is concealing if Bob learns essentially nothing about $b$ before the opening, and binding if Alice cannot change her mind after the…

Two resources can be extracted from many copies of a shared quantum state $\rho$: pure entanglement (Bell pairs, at the rate $E_D$, the distillable entanglement) and a secret key that an eavesdropper holding the rest of the world cannot learn (at the rate $K_D$, the distillable key). One always has $K_D \ge E_D$, because Bell pairs can be measured to give key.…

Two long standing open problems in quantum theory are to characterize the class of initial system-bath states for which quantum dynamics is equivalent to (1) a map between the initial and final system states, and (2) a completely positive (CP) map. The CP map problem is especially important, due to the widespread use of such maps in quantum information…

For addressing optimisation tasks on finite dimensional quantum systems, we give a comprehensive account of the foundations of gradient flows on Riemannian manifolds including new developments: we extend former results from Lie groups such as the full unitary group to closed subgroups like partitionings by factorisation into tensor products, where the…

In quantum mechanics, a fundamental law prevents quantum communications to simultaneously achieve high rates and long distances. This limitation is well known for point-to-point protocols, where two parties are directly connected by a quantum channel, but not yet fully understood in protocols with quantum repeaters. Here we solve this problem bounding the…

A 2-group is a categorified group: a monoidal category in which every object and every morphism is invertible. When the associativity and unit laws hold as equalities rather than up to isomorphism, the 2-group is called strict. Strict 2-groups appear as the fundamental 2-groups of homotopy 2-types, as symmetry objects of gauge theories with higher form…

A density operator $\rho$ on $\mathbb C^d$ describes a quantum system completely, but it cannot be read off a single copy: it has to be estimated from many identically prepared copies. Its spectrum $r_1 \ge \dots \ge r_d \ge 0$, $\sum_\alpha r_\alpha = 1$, is the part of $\rho$ that does not depend on a basis. It determines the entropy and purity of the state and the…

The no-cloning theorem says that no physical process turns an unknown quantum state $|\psi\rangle$ into two copies $|\psi\rangle|\psi\rangle$. Once perfect copies are excluded, the quantitative question is how good two imperfect copies can be, and how the quality of one copy trades off against the quality of the other. The answer bounds what an eavesdropper on…

A quantum channel has many capacities, one for each kind of information sent and each auxiliary resource allowed: classical bits or qubits, with or without shared entanglement, with or without a free classical side channel. Comparing these capacities is how quantum Shannon theory locates the value of each resource. Some comparisons look as if they should be…

Suppose a quantum system has been prepared $n$ times, either always in the state $\rho_0$ (with prior probability $\pi_0$) or always in the state $\rho_1$ (with prior $\pi_1$), and the task is to guess which. Helstrom's formula gives the smallest error probability over all measurements,

Two parties who do not share a reference frame can align one by sending quantum systems through an unknown rotation. Mathematically, a device applies an unknown matrix $g\in\mathrm{SU}(2)$ to each of $n$ qubits, and the task is to estimate $g$ from one measurement on the output. How fast the smallest achievable error falls with $n$ is a basic question of quantum…

Coding theorems and (strong) converses for memoryless quantum communication channels and quantum sources are proved: for the quantum source the coding theorem is reviewed, and the strong converse proven. For classical information transmission via quantum channels we give a new proof of the coding theorem, and prove the strong converse, even under the…

A quantum computer executes a fixed, finite instruction set of gates, while quantum algorithms are written with arbitrary gates. Every algorithm must therefore be compiled: each gate $U$ is replaced by a sequence of available instructions whose product approximates $U$. If an accuracy $\delta$ required sequences of length $O(1/\delta)$, compiling an $m$-gate…

The data processing inequality (DPI) for the conditional von Neumann entropy says that discarding part of the side information cannot make a quantum system less uncertain: for every tripartite state $\rho_{ABC}$,