The Quantum Formalization Drive

Approximating a partition function $Z(\beta)=\sum_{x\in\Omega}e^{-\beta H(x)}$ is a central task in statistical physics and in counting: it covers the Ising and Potts models, and, at $\beta=\infty$, counting the zero-energy configurations of a Hamiltonian, for instance the proper $k$-colourings of a graph. Computing $Z(\infty)$ exactly is #P-complete in many cases,…

Quantum error correction and quantum communication both ask the same question: after a known noise process $\mathcal A$ has acted on a quantum system, how well can its effect be undone? For a given noise model the best recovery is the solution of a semidefinite program, which gives a number but no structure and no formula. Barnum and Knill showed in 2000 that…

Quantum algorithms for semidefinite programming need a way to use an input matrix inside a quantum circuit. In the quantum state input model, an oracle prepares a purification of a density operator. In the quantum operator input model, a unitary instead exposes that operator as a block of a larger unitary. The two kinds of access serve different…

Phase estimation asks: given access to a unitary $U$ and an eigenvector $|u\rangle$ with $U|u\rangle = e^{2\pi i\varphi}|u\rangle$, determine $\varphi \in [0,1)$. It is the subroutine behind Shor's factoring algorithm, quantum chemistry energy estimation, and amplitude estimation, and is one of the standard sources of quantum speed-up.

This mission develops Chapter 7 of Quantum Algorithms and Learning Theory — Part II by Srinivasan Arunachalam. The chapter's selected results describe the mathematical guarantees below.

This mission develops Chapter 4 of Stabilizer Codes and Quantum Error Correction by Daniel Gottesman. The chapter's selected results describe the mathematical guarantees below.

This mission develops Chapter 15 of Quantum Computing: Lecture Notes by Ronald de Wolf. The chapter's selected results describe the mathematical guarantees below.

This mission develops Chapter 4 of Quantum Computing: Lecture Notes by Ronald de Wolf. The chapter's selected results describe the mathematical guarantees below.

This mission develops Chapter 24 of Lecture Notes on Quantum Algorithms by Andrew Childs. The chapter's selected results describe the mathematical guarantees below.

A local quantum system is built from degrees of freedom placed at sites of a lattice. Its Hamiltonian may contain many terms, each acting on a small group of sites. Even though a term is local, time evolution can spread an observable beyond its original support. A Lieb–Robinson bound limits the size of a commutator between the evolved observable and one…

Maximizing a homogeneous polynomial $p$ over the unit sphere, $p_{\max}=\max_{x\in S^{d-1}}p(x)$, covers the largest stable set of a graph (degree three), the $2\to4$ norm of a matrix (degree four) and the best separable state problem of quantum information. For quadratic $p$ it is an eigenvalue problem; for degree at least three it is NP-hard. The sum-of-squares…

The quantum linear systems problem asks, given a sparse Hermitian $N \times N$ matrix $A$ with condition number $\kappa$ and a procedure preparing a state $|b\rangle$, to prepare a state close to $A^{-1}|b\rangle / \|A^{-1}|b\rangle\|$. Harrow, Hassidim and Lloyd (2009) gave a quantum algorithm whose running time is polynomial in $\log N$ and $\kappa$ but grows like …

In ordinary quantum mechanics, and in quantum field theory on a fixed spacetime, events happen in a definite causal order: an operation either precedes another, follows it, or the two are spacelike separated. Attempts to combine quantum theory with general relativity call this assumption into question. In general relativity the causal structure is…

Whether the many-worlds (Everett) interpretation of quantum mechanics is local in the sense of Bell is a recurring question in the foundations of physics. A number of authors have argued that Everett's theory escapes Bell-type nonlocality theorems because it drops the assumption that each measurement has a single outcome. A. Drezet's paper arXiv:2306.07794 (…

Many classical search algorithms are random walks: a Markov chain $P$ on a finite state space $X$ is run until it hits a marked state. Szegedy (2004) attached to every such chain a unitary quantum walk $W(P)$, and Magniez, Nayak, Roland and Santha (SIAM J. Comput. 2011, arXiv:quant-ph/0608026) used it to search quadratically faster than the classical walk for…

Bounded-error factoring and exact factoring have different correctness requirements. Repetition until success and increasingly accurate rotations do not automatically give a fixed-gate, worst-case polynomial exact algorithm. The pinned manuscript supplies the research context.

Character sums express phase constraints on complex Hadamard matrices. In dimension six these constraints also bear on how many mutually unbiased bases can coexist. The pinned manuscript supplies the research context.

Shannon's entropy power inequality bounds the entropy of a sum of independent random vectors below by the entropies of the summands; it is a basic tool for classical Gaussian channel capacities. In optical communication, addition is replaced by passive mixing of bosonic modes at a beam splitter. Guha, Erkmen and Shapiro conjectured the sharp bosonic…

An oracle lets an algorithm ask for the value of a function without giving it a description of that function. An oracle lower bound isolates how many questions are needed, even when computation between questions is unrestricted. Bennett, Bernstein, Brassard and Vazirani used this viewpoint to compare classical and quantum access to randomly chosen functions…

Two observers, Alice and Bob, share a quantum system. Alice performs some intervention (a measurement, possibly followed by discarding part of her apparatus) and Bob, somewhere else, performs his own. If the statistics of Bob's outcomes could depend on what Alice chose to do, Alice could send Bob a message through the shared system alone, and if the two…

A mixed state of a $D$-dimensional quantum system is a $D\times D$ positive semidefinite matrix $\rho$ of trace $1$. Writing $\rho$ down takes about $D^2$ real numbers, and $D$ is exponential in the number of qubits, so learning $\rho$ in full is expensive. Holevo's theorem and the random access code bounds of Ambainis, Nayak, Ta-Shma and Vazirani say that an $n$-qubit state…

Shadow tomography asks for predictions of many specified measurements of an unknown quantum state, while using as few prepared copies of that state as possible. The requested output is a list of acceptance probabilities, not a full description of the state. A procedure might exploit the fact that these are only $M$ numbers, even when the state has dimension $D$.…

The security of the RSA cryptosystem rests on the assumed difficulty of factoring large integers, and the best known classical algorithms for factoring run in super-polynomial time. In 1994 Peter Shor showed that a quantum computer can factor an $n$-digit integer in time polynomial in $n$ (Shor, SIAM J. Comput. 1997; conference version FOCS 1994). The algorithm…

The Hamiltonian of a single nonrelativistic particle in $\mathbb R^n$ moving in a potential $V$ is the Schrödinger operator $H = -\Delta + V$ acting in $L^2(\mathbb R^n)$. Before anything can be said about the dynamics or the energy levels of such a particle, one must know that $H$ is a genuine observable: a self-adjoint operator on a specified domain. For potentials…

In quantum mechanics the state of a system at time $t$ is $\psi(t) = \mathrm e^{-\mathrm itA}\psi$, where the Hamiltonian $A$ is a self-adjoint operator. The spectral theorem splits the Hilbert space into subspaces according to the type of the spectral measure of a vector (absolutely continuous, singularly continuous, pure point). That splitting is defined…