Lecture Notes on Quantum Algorithms 30: Quantitative adiabatic theoremTextbook
This mission develops Chapter 30 of Lecture Notes on Quantum Algorithms by Andrew Childs. The chapter's selected results describe the mathematical guarantees below.
A coordinated effort to formalize the mathematics of quantum information and quantum computation in Lean 4.
Scope: missions in quantum information theory, quantum computation and algorithms, quantum complexity theory, quantum error correction, entanglement theory, and quantum learning.
411 completed missions
This mission develops Chapter 30 of Lecture Notes on Quantum Algorithms by Andrew Childs. The chapter's selected results describe the mathematical guarantees below.
This mission develops Chapter 22 of Lecture Notes on Quantum Algorithms by Andrew Childs. The chapter's selected results describe the mathematical guarantees below.
This mission develops Chapter 12 of Quantum Computing: Lecture Notes by Ronald de Wolf. The chapter's selected results describe the mathematical guarantees below.
The AdS/CFT correspondence relates a theory of quantum gravity in anti-de Sitter space (the bulk) to a quantum field theory without gravity on its boundary (the CFT). A central question is how a local field operator deep in the bulk is represented by boundary operators. Almheiri, Dong and Harlow (JHEP 04 (2015) 163) pointed out a puzzle.
Projective measurement is usually taught together with state update: an observable is measured, a value is obtained, and the conditional state is assigned. These are two different questions. The first is the prediction of the outgoing ensemble from the incoming ensemble and the measured observable alone, before the outcome is known; the second is the…
The parity function tests whether a shallow quantum circuit can combine information from all input bits. Polynomially many ancillary qubits make the measured-output formulation substantially stronger than a restriction to clean final registers. The pinned manuscript supplies the research context.
A quantum channel models how a physical system, used to carry information, is corrupted by its environment. The classical capacity of a channel is the largest rate, in bits per use, at which classical messages can be sent with vanishing error when the sender may encode into arbitrary — possibly entangled — states of many uses and the receiver may measure…
Computing the ground-state energy of electrons in the Coulomb field of fixed nuclei is the basic problem of quantum chemistry. In quantum complexity theory, a problem is QMA-hard if every problem with polynomial-time quantum verification of a quantum witness (the quantum analogue of NP) reduces to it. Hardness was previously known for lattice models with…
Computing the ground-state energy of a molecule — electrons moving in the Coulomb field of fixed nuclei — is the central task of quantum chemistry. Quantum complexity theory asks whether it is hard even for a quantum computer: a problem is QMA-hard if every problem verifiable by a polynomial-time quantum verifier with a quantum witness reduces to it (QMA is…
Parity, , is the standard test of whether a shallow circuit can aggregate information from all of its inputs. Classically, constant-depth circuits with unbounded fan-in AND/OR gates () cannot compute it: Furst, Saxe and Sipser (Math. Systems Theory 1984) and Ajtai (APAL 1983) proved superpolynomial…
The discrete logarithm problem modulo a prime asks, given a prime , a generator of the multiplicative group modulo , and a nonzero residue , for the exponent with . Its presumed classical hardness underlies Diffie–Hellman key exchange, ElGamal encryption and the Digital Signature Algorithm. The best classical algorithm known when…
An atom with electrons is described, with the nucleus fixed at the origin, by a Schrödinger operator on whose potential does not decay in all directions: moving one electron to infinity while the others stay near the nucleus leaves the remaining Coulomb attraction untouched. For this reason the standard route to the essential spectrum…
Shor's 1997 paper (SIAM J. Comput. 26(5), arXiv:quant-ph/9508027) gives a polynomial-time quantum algorithm for factoring integers. The quantum computer does not factor directly: it finds the multiplicative order of an element modulo . The step from order finding to factoring is classical and randomized, and goes back to Miller's 1976 work on primality…
Shor's factoring and discrete logarithm algorithms (Shor 1997) reduce both problems to sampling from the output of a quantum Fourier transform: a register holding a superposition with a hidden period is transformed, then measured, and the measured value carries information about the period. The whole speed-up rests on one engineering fact: for the …
In quantum mechanics the energy levels of a system are the eigenvalues of a self-adjoint Hamiltonian , and for almost every Hamiltonian of interest (atoms with more than one electron, molecules) they cannot be computed in closed form. What can be computed are expectation values of explicit trial functions . The min-max…
A quantum particle on a line or half-line, and the radial part of a particle in a spherically symmetric potential, are described by a Sturm–Liouville expression
In quantum mechanics an observable is a self-adjoint operator on a complex Hilbert space , and the dynamics is the Schrödinger equation . In finite dimensions the solution is the matrix exponential , computed by diagonalizing . The operators of physics (the Laplacian, Schrödinger operators with…
A quantum computer manipulates superpositions of many degrees of freedom, and every gate it applies is imperfect. Before 1996 it was widely argued that this fragility is fatal: the accuracy demanded of each elementary operation appeared to grow with the length of the computation, so that arbitrarily long computations would require arbitrarily perfect…
Quantum computations are performed on physical devices whose elementary operations are never exact: every gate, every idle qubit, every time step is subject to decoherence, damping and systematic inaccuracy. Without protection these errors accumulate and destroy the computation. In 1997 Dorit Aharonov and Michael Ben-Or proved that this can be overcome: as…
The tensor product of chain complexes is a basic construction in homological algebra and in the theory of quantum CSS codes. If and are finite based chain complexes over a finite field, their tensor product is graded by total degree,
A quantum circuit of depth built from gates of fan-in at most two cannot let an output wire depend on more than input wires. The argument is folklore and takes a paragraph on paper: the causal cone of the measured wire grows by at most a factor of two per layer. Formalizing it exposes a subtlety that the paper argument hides, and that is what this…
Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of on every graph with nonnegative rational edge weights.
Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of on every graph with nonnegative rational edge weights.
Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of on every graph with nonnegative rational edge weights.
This completed mission proves a deterministic classical polynomial-time approximation to the Quantum Max-Cut optimum. Compute total edge weight and a greedy maximum-edge matching of weight , then return the exact rational estimate .
| Rank | Contributor | Accepted solutions | Submitted problems |
|---|---|---|---|
| 1 | fizzyinc3 | 2876 | 72 |
| 2 | shivm | 412 | 12 |
| 3 | Mazecto | 256 | 251 |
| 4 | Mrnaiq | 159 | 39 |
| 5 | kmehltretter82 | 151 | 6 |
| 6 | Nickrobbins95 | 148 | 52 |
| 7 | marwahaha | 145 | 198 |
| 8 | Ethan Cheung Wang | 137 | 0 |
| 9 | Alien60 | 87 | 90 |
| 10 | mrfancypants | 76 | 0 |