PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

Scott Aaronson

arXiv:1607.05256v1quant-phcs.CCgr-qc

TL;DR

The course asks how difficult it is to prepare quantum states and apply unitary transformations, using quantum complexity as a unifying framework. It develops this framework through quantum information and computation, then connects it to proofs and advice, quantum money, black-hole information, and AdS/CFT. The notes include classical-simulation results, including PQP = PP for suitable exact gate sets, while also identifying concrete limitations in quantum-state sampling and quantum-money verification.

  • Problem

    The course examines how hard it is to create a given quantum state or apply a given transformation, rather than focusing only on decision problems.

  • Method

    It systematically studies quantum state and unitary complexity and uses them as a connecting thread across quantum computing, quantum money, black holes, and AdS/CFT.

  • Results

    For gate choices with entries in {0, ±1/2, ±1}, the notes state that the classical simulation extends to PQP and yields PQP = PP.

  • Takeaways & Limitations

    Quantum state and unitary complexity provides a common framework for discussing quantum proofs and advice, quantum money, black-hole information, and AdS/CFT.

  • Takeaways & Limitations

    The QSampling construction does not produce |ψ_D⟩ because its |r⟩ register is necessarily decohering garbage.

Abstract

from arXiv · show

These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21-25, 2016. The focus is quantum circuit complexity---i.e., the minimum number of gates needed to prepare a given quantum state or apply a given unitary transformation---as a unifying theme tying together several topics of recent interest in the field. Those topics include the power of quantum proofs and advice states; how to construct quantum money schemes secure against counterfeiting; and the role of complexity in the black-hole information paradox and the AdS/CFT correspondence (through connections made by Harlow-Hayden, Susskind, and others). The course was taught to a mixed audience of theoretical computer scientists and quantum gravity / string theorists, and starts out with a crash course on quantum information and computation in general.

Lecture 1

Lecture 1 introduces quantum states, unitary transformations, and measurements, then frames quantum state and unitary complexity as a common lens for topics across quantum computing and quantum gravity.

  • Quantum state complexity asks how many operations are needed to prepare a given quantum state.
  • Unitary transformation complexity asks how many operations are needed to apply a given unitary transformation.
  • The course uses state and unitary complexity as a connecting thread across quantum proofs and advice, quantum money, black-hole information, and AdS/CFT.
  • Quantum states: An N-dimensional quantum state is a unit vector over C^N, represented as a superposition of basis states with normalized complex amplitudes.
  • Quantum operations: Unitary transformations preserve inner products and norms, mapping quantum states to quantum states.
  • Quantum information principles: The No Communication Theorem states that Alice’s operations cannot change Bob’s local density matrix when they share a bipartite state.
  • Quantum information principles: Trace distance bounds how much a two-outcome measurement’s acceptance probability can change between nearby mixed states.
  • Quantum information principles: The Almost As Good As New Lemma analyzes how a high-probability measurement outcome constrains the disturbance caused by the measurement procedure.

Lecture 2

Lecture 2 develops basic quantum-circuit concepts, including cloning, entanglement, gate universality, and circuit complexity, and contrasts quantum and classical computational power.

  • Quantum mechanics principles: The No-Cloning Theorem states that no procedure can map an arbitrary state |ψ⟩ to two copies |ψ⟩⊗2.
  • Quantum mechanics principles: Cloning would require a nonlinear transformation on superpositions, which cannot be unitary; more generally, it would increase trace distance, which superoperators cannot do.
  • Entanglement: The example distinguishes Bob and Charlie’s unentangled mixed state from Alice and Bob’s entangled pure Bell-pair state.
  • Entanglement: Monogamy of entanglement says that maximal entanglement between Alice and Bob excludes entanglement and classical correlation between Alice and Charlie.
  • Entanglement measures: Distillable entanglement counts EPR pairs obtainable by local operations and classical communication, whereas entanglement of formation counts pairs needed to create a state.
  • Quantum circuits: For almost all n-qubit unitaries, exact circuit complexity satisfies C(U) ≥ 4^n, and an explicit construction makes this approximately tight.
  • Quantum circuits: A gate set is universal when its gates approximate any unitary on any number of qubits to arbitrary precision; examples include {Toffoli,H,Phase}.
  • Classical simulation: Quantum computers are at least as powerful as classical computers and at most exponentially more powerful, while PQP equals PP for suitable exact gate sets.

Lecture 3

Lecture 3 develops the Hidden Subgroup Problem as a framework connecting Simon’s and Shor’s algorithms to quantum query and circuit complexity. It then examines why strong complexity lower bounds for explicit states and unitaries are difficult, and how state complexity relates to standard complexity assumptions.

  • Hidden Subgroup Problem: The Hidden Subgroup Problem asks for a hidden subgroup from black-box access to a function constant and distinct on subgroup cosets.Simon’s problem is the special case over Z_n, while Shor’s factoring algorithm uses a classical reduction to Period-Finding.
  • Hidden Subgroup Problem: O(1) queries suffice for quantum Period-Finding, placing Integer Factoring in BQP.The quantum step uses a discrete Fourier transform and truncates the infinite integer domain to a finite part.
  • Hidden Subgroup Problem: For every finite abelian group G, HSP(G) is in BQP_f, while general HSP(G) is solvable with O(log^2 |G|) quantum queries.The latter query-efficient algorithm applies to arbitrary finite groups, but its post-processing may not be efficient.
  • Hidden Subgroup Problem: Non-abelian HSP algorithms remain limited, despite connections to Graph Isomorphism and Approximate Shortest Lattice Vector.Known successes mostly concern groups that are close to abelian groups, such as the Heisenberg group.
  • Circuit Complexity: The EHK measurement raises the open problem of proving exponential lower bounds for explicitly given unitary matrices and avoiding natural-proof barriers.It is unknown whether polynomial-size circuits can produce matrices indistinguishable from Haar-random unitaries by sufficiently powerful classical algorithms under standard assumptions.
  • Circuit Complexity: Counting shows that almost every Boolean-function unitary and almost every n-qubit state has exponential approximate circuit complexity.By contrast, BQP functions have polynomial-complexity unitaries, so strong lower bounds for explicit functions could imply standard complexity-class separations.
  • Quantum State Complexity: A maximally entangled state can have trivial O(n) complexity, and linear combinations can behave very differently from their component states.The notes emphasize that complexity is not generally preserved under linear combination; an explicit preparation can also require an ancilla.
  • Quantum State Complexity: Preparing explicit states with superpolynomial complexity may require proving BQP ≠ P^#P, whereas analogous unitary lower bounds might avoid that assumption.For essentially all explicit states discussed, BQP = P^#P would imply polynomial circuit complexity.

Lecture 4

Lecture 4 studies QSampling states, showing how garbage-free state preparation connects distributional quantum states to Graph Isomorphism and Statistical Zero-Knowledge. It then surveys quantum proofs, local Hamiltonians, and group-membership protocols, emphasizing both algorithmic power and preparation limitations.

  • QSampling States: A QSampling state encodes an efficiently samplable distribution D as a quantum superposition weighted by the square roots of its probabilities.A classical sampler can prepare a related state, but its random-seed register becomes decohering garbage rather than the desired QSampling state.
  • QSampling States: Nuclear waste—the sampler’s seed register—prevents the efficiently generated state from being the intended QSampling state.Removing this garbage is not generally known, and in some settings may require additional assistance.
  • QSampling States: QSampling states can be prepared efficiently for some distributions, including near-uniform superpositions over perfect matchings of a bipartite graph.This construction relies on examining the Markov Chain Monte Carlo algorithm used to sample perfect matchings.
  • Graph Isomorphism: If a QSampling state for each graph can be prepared uniformly in polynomial time, Graph Isomorphism is in BQP.The test prepares graph-associated states and uses a control-qubit measurement to distinguish equality from orthogonality.
  • Graph Isomorphism: Preparing QSampling states for Graph Isomorphism remains unclear in less than exponential time, even after Babai’s quasipolynomial Graph Isomorphism algorithm.The obstacle is state preparation, not merely the existence of an efficient classical decision procedure.
  • QSampling States: If NP ⊆ BQP, every efficiently samplable distribution has a QSampling state preparable to 1/n^O(1) precision in polynomial complexity.This is weaker than the BQP = P^#P assumption previously associated with efficiently preparing many explicit states.
  • QSampling States: Efficient preparation of QSampling states would imply SZK ⊆ BQP, using their relationship to Statistical Difference.Statistical Difference is complete for SZK and compares efficiently samplable distributions that are either close or far apart.
  • Query Complexity: There are oracle separations showing SZK is not contained in BQP and NP is not contained in BQP, while Collision requires Ω(N^1/3) quantum queries.The collision lower bound is tight according to the notes.

Lecture 5

Lecture 5 examines whether quantum proofs and advice provide power beyond classical information, using QCMA, QMA, postselection, and oracle separations. It presents separations and simulations while highlighting open questions about preparing quantum witnesses and advice states.

  • QCMA and QMA: QCMA restricts Merlin to classical witnesses while retaining quantum verification, so QCMA ⊆ QMA.This makes QCMA a quantum generalization of NP and a comparison class for quantum proofs.
  • QCMA and QMA: Finding an oracle A with QCMA^A ≠ QMA^A remains open, although quantum-oracle and Group Non-Membership results provide partial progress.Group Non-Membership has a QCMA protocol using polylogarithmic oracle queries but exponential post-processing, preventing a query-complexity lower bound.
  • Oracle results: There exists a quantum oracle U such that QMA^U ≠ QCMA^U, and another such oracle separates BQP^U/qpoly from BQP^U/poly.These oracle results establish separations between quantum and classical forms of proof or advice in relativized settings.
  • Amplitude amplification: O(1/ε) queries suffice for amplitude amplification when the initial and target states have overlap ε.The iterates remain in a two-dimensional subspace, and each reflection increases the relevant angle by approximately ε.
  • Quantum witness preparation: Preparing every accepting QMA witness with a polynomial-size quantum circuit would imply QMA = QCMA, but the converse is unknown.The same witness-preparation assumption would also imply BQP/poly = BQP/qpoly.
  • Quantum advice and postselection: PostBQP = PP, while BQP/qpoly ⊆ PostBQP/poly = PP/poly and BQP/qpoly ⊆ QMA/poly.Quantum advice therefore has classical-advice upper bounds, despite the proposition PQP/qpoly = ALL for unbounded-error quantum computation.
  • Quantum advice and postselection: If PostBPP = PostBQP, then the polynomial hierarchy collapses to its third level, providing evidence that the classes differ.The notes connect this consequence to Toda’s theorem and contrast it with the weaker evidence available for BPP versus BQP.

Lecture 6

Lecture 6 introduces black holes and the puzzles that motivate connecting black-hole physics with computational complexity. It emphasizes the event horizon, singularity, and the information problem as a bridge back to complexity theory.

  • Black holes and complexity: The lecture uses black-hole puzzles to connect a break from complexity theory back to complexity.The stated focus is the black-hole information problem and its relation to computational questions.
  • Black holes and complexity: A black hole has a central singularity and an event horizon, inside which no signals can escape.The event horizon is described as a causal boundary surrounding the singularity.
  • Black holes and complexity: General relativity predicts that sufficiently concentrated mass collapses into a black hole, and LIGO supplied direct evidence for black holes shortly before the lectures.The notes place these physical facts before introducing the theoretical puzzles.

6.1 Thermodynamics and Reversibility

This section presents black holes as a thermodynamic and reversibility puzzle: Hawking radiation appears thermal and information-independent, conflicting with an expected unitary evolution. Bekenstein’s entropy bound makes black holes maximally dense information stores, while evaporation is extremely slow.

  • Thermodynamics and entropy: Black holes appear to threaten the Second Law because matter thrown inside seems to disappear, apparently decreasing accessible entropy.The puzzle arises because microscopic physical laws are reversible while black holes seem to act as entropy sinks.
  • Thermodynamics and entropy: Bekenstein proposed that black-hole entropy scales with event-horizon area rather than volume.The notes give an approximate storage density of 10^69 bits per square meter.
  • Thermodynamics and entropy: 10^69 bits per square meter is described as the maximum entropy density allowed for a physical system with a given surface area.On this account, black holes are the most compact possible information stores, though retrieval is poor.
  • Hawking radiation: Hawking’s semiclassical calculation predicts slowly escaping thermal radiation from black holes.The radiation is described through an external observer’s measurements near the event horizon.
  • Hawking radiation: A solar-mass black hole’s evaporation time is approximately 10^67 years, scaling as r^3 or A^3/2.The stored-bit count instead scales as the horizon area A ∼ r^2.
  • Hawking radiation: Hawking radiation is predicted to be uncorrelated with the details of infalling matter, so pure input information appears to emerge as mixed thermal radiation.This creates a conflict with treating physical evolution as one large unitary transformation.

6.2 The Xeroxing Problem

The Xeroxing Problem asks how information can be recovered outside a black hole without producing a second copy inside. Black-hole complementarity addresses this by identifying the inside and outside descriptions as the same qubit viewed differently.

  • The Xeroxing Problem: The Xeroxing Problem arises because an infalling qubit appears to remain inside while its information could later emerge in Hawking radiation.The thought experiment compares the perspectives of an observer who falls in and one who remains outside.
  • Black-hole complementarity: Black-hole complementarity says the qubit is not cloned because no single observer can access both apparent copies.For an outside observer waiting for evaporation, the inside manifestation reaches the singularity before the observer can enter.
  • Black-hole complementarity: The inside and outside qubits are proposed to be literally the same qubit, measured or viewed in two different ways.This proposal is attributed to Susskind and ’t Hooft.

6.3 The Firewall Paradox

The firewall paradox combines Hawking-radiation entanglement with the smooth-horizon prediction, producing an apparent violation of entanglement monogamy. After the Page Time, information-theoretic scrambling lets an outside observer recover correlations with an outgoing qubit, forcing competing resolutions.

  • Scrambling and the Page Time: After k > n/2 qubits emerge from a Haar-random n-qubit state, the reduced state is no longer maximally mixed, and each selected emitted qubit is typically entangled with the others.For k < n/2, the reduced state is close to maximally mixed; the behavior changes after half the qubits have emerged.
  • Alice’s experiment: Alice’s experiment models the black hole as a known unitary evolution whose Hawking radiation is captured and processed while the interior remains inaccessible.At 2n/3 emitted qubits, the registers are R for earlier radiation, B for the next outgoing qubit, and H for the remaining interior qubits.
  • Alice’s experiment: A unitary acting only on R can, in principle, distill a Bell pair between B and one qubit of R, after which Alice measures the pair and enters the black hole.This creates the conflict: smooth-horizon physics requires B-H entanglement, while the decoding procedure establishes B-R entanglement.
  • The paradox: The firewall paradox arises because an outgoing Hawking qubit B is predicted to be entangled both with earlier radiation R and with an interior partner H.Quantum field theory predicts short-range entanglement across the horizon, while the scrambled-state analysis predicts entanglement between B and R after the Page Time.
  • Possible resolutions: Proposed resolutions include abandoning access to the interior, introducing a firewall, giving up unitarity, or making the firewall depend on Alice’s extraordinary radiation-processing experiment.The fourth option treats the interior register H as not independent from R and B, invoking black-hole complementarity.

6.4 The HH Decoding Task

The Harlow-Hayden Decoding Task asks for a unitary on accessible radiation that extracts a Bell pair with the next outgoing qubit. Although such a unitary exists information-theoretically, constructing it may require exponential resources, with major consequences for the firewall thought experiment.

  • Task definition: The HH Decoding Task takes a circuit C preparing a tripartite state |ψ⟩RBH and asks for a unitary on R that creates a Bell pair between B and a designated qubit of R.The input circuit prepares the state from |0⟩⊗n, while B is a single qubit and H is the remaining register.
  • Computational difficulty: The desired decoding is information-theoretically possible but may be computationally intractable for scrambled states.Abstract dimension-counting arguments establish the needed entanglement, but extracting an explicit circuit from them can yield exponential size.
  • Computational difficulty: The known preparation circuit C does not remove the difficulty, because Alice must uncover the structure by acting only on R rather than accessing all three registers.With access to R, B, and H, applying C^-1 would be easy; the restriction to R is essential.
  • Complexity consequence: If arbitrary HH Decoding instances were solvable in polynomial time, then SZK would be contained in BQP.This conditional theorem supplies a complexity-theoretic reason to doubt a general efficient decoder.
  • Physical interpretation: Under the stated hardness implication, preprocessing Hawking radiation for a solar-mass black hole would take roughly 2^1067 years rather than roughly 10^67 years.The course notes interpret this as exceeding the black hole’s useful lifetime, preventing Alice from carrying out the firewall experiment in time.

6.5 The Harlow-Hayden Argument

The Harlow-Hayden argument reduces established quantum-hard problems to the task of decoding radiation-held entanglement. Its refinements derive hardness from quantum-secure one-way functions and extend the obstruction from entanglement to even classical correlation, while generic black-hole states remain an open case for state-complexity evolution.

  • Query complexity: For black-box Set Equality, quantum algorithms require Ω(N^1/3) queries, and Zhandry’s lower bound is tight.This strengthens Aaronson’s earlier Ω(N^1/7) lower bound.
  • Reduction from Set Equality: The reduction encodes Set Equality into an HH state so that equal ranges permit Bell-pair decoding, whereas disjoint ranges make the decoding promise fail.A successful Bell-pair test occurs with probability 1 in the equal-range case and at most 1/2 in the disjoint-range case.
  • Reduction from Set Equality: Therefore, an efficient HH decoder would solve Set Equality in quantum polynomial time, so hardness of Set Equality implies hardness of HH Decoding.Set Equality is also related to Collision and Statistical Difference, and efficient quantum Statistical Difference would imply SZK ⊆ BQP.
  • Physical interpretation: The argument relies on black holes both to hide H from Alice and to scramble the infalling qubits, although other physical systems could also provide scrambling.Its proposed significance is a possible breakdown of field-theoretic reasoning in a regime of exponential computational complexity rather than at Planck energy.
  • Improvements: Aaronson’s refinement shows that if injective one-way functions are quantum-hard to invert, then the HH Decoding Task is hard.The assumption is weaker in form than relying directly on SZK not being contained in BQP.
  • Improvements: The same one-way-function assumption makes it hard even to distill classical correlation between R and B, not merely quantum entanglement.Detecting such correlation would enable prediction of a hardcore bit and thereby inversion of the one-way function.
  • Preskill’s problem: The formal reductions do not settle whether generic black-hole states admit exponentially long decoding circuits with only polynomial state complexity throughout.For the special Set Equality and one-way-function constructions, exponential-time decoding can keep the intermediate state complexity near that of the initial state; the generic case remains open.

Lecture 7

Lecture 7 develops the AdS/CFT connection between quantum circuit complexity and wormhole geometry, then examines why proving the predicted complexity growth is difficult. It presents conditional superpolynomial lower bounds while emphasizing that the complexity–wormhole correspondence remains speculative.

  • AdS/CFT and Complexity: AdS/CFT is presented as a conjectured duality between quantum gravity in AdS spacetime and a lower-dimensional conformal field theory.The CFT can be discretized and idealized as a quantum circuit acting on finitely many qubits.
  • AdS/CFT and Complexity: Circuit complexity is proposed as an intrinsic clock for quantum states, with the state complexity Cε(|ψt⟩) expected to track a growing function of time.The notes say circuit complexity is currently the only principled candidate for recovering time from a quantum state.
  • Complexity Growth: Applying a simple unitary U repeatedly can make state complexity grow approximately linearly until about t ≈ 2^n, after which it cannot keep increasing indefinitely.The notes describe later dips when random-looking states return near low-complexity states.
  • Complexity Growth: Reversing U makes the complexity shrink at the same speed, while inserting an unrelated unitary V before reversal is expected to preserve continued growth.These behaviors are presented as matching corresponding predictions for wormhole evolution.
  • Limitations: The complexity–wormhole-volume duality is speculative because an observed correlation need not be causal, and the relevant complexity variant is not uniquely determined.Open choices include exact versus approximate complexity, ancilla use, and whether garbage must be uncomputed.
  • Lower Bounds: A rigorous linear-growth lower bound remains open, because known arguments would imply major complexity-class separations.For example, superpolynomial state complexity can imply PSPACE ⊄ BQP/poly, while the theorem gives superpolynomial complexity for some t > cn unless PSPACE ⊂ PP/poly.

Lecture 8

Lecture 8 studies private-key quantum money, beginning with Wiesner’s unconditionally secure but storage-intensive scheme and its computationally secure BBBW refinement. It then examines counterfeiting attacks, security–storage limits, and a connection between quantum money and black-hole decoding.

  • Money Schemes: Quantum money must be both unclonable and verifiable, using quantum states to exploit the No-Cloning Theorem.Wiesner’s scheme assigns each note a classical serial number and an associated n-qubit state.
  • Counterfeiting: (3/4)^n is the tight success probability for a strategy that generates two entangled notes both passing verification.The bound was established using semidefinite formulations of the counterfeiter’s problem.
  • Security Limitations: The Wiesner and BBBW analyses cited here are not full security proofs because they do not cover counterfeiters who begin with multiple legitimate banknotes.The notes describe this as a limitation of the earlier results, with later unpublished work addressing general security.
  • Wiesner and BBBW: Wiesner’s scheme is unconditionally secure but requires a large database, whereas BBBW stores one secret key by replacing the random function with a pseudorandom function.The BBBW construction is computationally secure and avoids the database of all issued banknotes.
  • Security–Storage Tradeoff: Storing only n bits allows an exponential-time quantum counterfeiter to break a scheme using poly(n) legitimate states and O(n) verification queries.Without verification queries, the counterfeiter can instead produce an output accepted with probability Ω(1/n).
  • Interactive Attacks: Interactive verification attacks can fully break Wiesner’s and BBBW’s schemes, as well as schemes using unentangled qubits verified by separate projective measurements.The attacks learn the hidden basis information through repeated trial verifications while keeping the disturbance controlled.
  • Quantum Money and Black Holes: A secure private-key injective quantum money scheme with small keys implies that the Harlow–Hayden decoding task is hard.Equivalently, the notes state that decoding Hawking radiation from a black hole would imply the ability to counterfeit quantum money.

Lecture 9

Lecture 9 develops public- and private-key quantum money schemes around query-complexity barriers to cloning hidden quantum states. It also presents oracle-relative constructions, reductions, and quantum attacks on noisy schemes.

  • Public-key quantum money: Public-key quantum money security reduces to securing a public-key mini-scheme when quantum-secure signatures are available.Any counterfeiter against the full scheme also breaks either the mini-scheme or signature scheme.
  • Oracle constructions: There exists a quantum oracle relative to which a public-key mini-scheme exists, with counterfeiting requiring Ω(2^n/2) queries.Producing a valid bill without a legitimate banknote takes O(2^n/2) queries by Grover search, and this is optimal.
  • Complexity-theoretic no-cloning: Ω(2^n/2) oracle queries are necessary to clone a Haar-random n-qubit state, even when given a reflection oracle and one copy.The bound matches the query complexity of Grover search for the state from scratch.
  • From public to private money: A classical oracle supports public-key quantum money, and this yields a private-key scheme secure against interactive attacks without computational assumptions.The private-key construction requires the bank to maintain a huge database.
  • Attacks: A quantum attack fully breaks the noisy low-degree polynomial scheme and recovers a hidden-subspace basis with success probability Ω(2^-n/2).The attack reduces the noisy scheme to the noiseless one and produces an algorithm specialized to extremely small success probabilities.

Lecture 10

Lecture 10 studies which unitaries a possibly non-universal gate set can generate, distinguishing physical universality from computational universality. It gives decidability and genericity results while highlighting limitations of Solovay–Kitaev for non-universal sets.

  • Physical universality: Physical universality means densely generating SU(2^n) on every sufficiently large number of qubits, rather than merely supporting quantum computation.A gate set may be computationally universal without being physically universal, such as one generating only SO(2^n).
  • Approximation limits: Solovay–Kitaev approximates any n-qubit unitary with O(exp(n) polylog(1/ε)) gates when the gate set is inverse-closed and approximately universal.Its efficient polylogarithmic dependence on 1/ε is useful, but the theorem does not apply to non-universal gate sets.
  • Decidability: Physical universality is decidable for gate sets with algebraic entries because an effective upper bound on the required qubit count can be computed.Ivanyos’s theorem bounds the test to O(kd^8) qudits, after which the gate-set closure can be computed.
  • Universality across system sizes: Universality on one n′≥2 qubit system implies universality on every larger n≥n′.The argument embeds a universal two-qubit gate as U⊗I^(n′−2).
  • Genericity: A Haar-random two-qubit gate is physically universal with probability 1.Thus non-universal gate sets form a measure-0 subset of all gate sets.

10.2 Difficulty of Classification

The classification problem asks which subgroup of SU(4) a two-qubit gate set generates, but the subgroup structure of SU(4) remains only partially characterized. Approximate generation requires considering topological closure.

  • Problem formulation: For an inverse-closed two-qubit gate set, the generated object is a closed subgroup S of SU(4).Closure is required because a unitary counts as generated when it is approached by a convergent sequence of circuits.
  • Classification challenge: Classifying possible generated subgroups is difficult because even the subgroup structure of SU(n) remains incomplete for small n.SU(3) classification was completed only in 2013, while infinite families of SU(4) subgroups remain poorly characterized.

10.3 Classification of Quantum Gates and Hamiltonians

Lecture 10 surveys classification results for two-level unitaries and Hamiltonian-generated gates. It combines universality theorems with separations between classical simulability and sampling hardness for commuting Hamiltonians.

  • Two-level unitaries: Two-level unitaries generate all of SU(n) for every n≥2.They act on pairs of basis states rather than following the usual tensor-product structure, with motivation from optical beamsplitters.
  • Two-level unitaries: A 2×2 determinant-−1 gate is classified into cases ranging from generating only trivial unitaries to densely generating SU(n) for all n≥3.The supplied classification lists the real SO(n) case and the fully SU(n)-generating case among its alternatives.
  • Hamiltonian universality: A 2-qubit Hamiltonian is universal without ancillas unless its evolution fails to generate entanglement or shares an eigenvector with SWAP.These two conditions are both necessary and sufficient exceptions.
  • Hamiltonian universality: The Lie-algebra closure of pairwise Hamiltonians provides a criterion for physical universality when it contains all Hermitian matrices.The closure is formed using real linear combinations and commutators.
  • Commuting Hamiltonians: Commuting Hamiltonians cannot be universal because generated unitaries remain diagonal in a common basis, yet some yield classically hard sampling tasks.Such sampling would be impossible in classical polynomial time unless the polynomial hierarchy collapses.
  • Commuting Hamiltonians: Any 2-qubit commuting Hamiltonian is either classically simulable or supports sampling beyond classical polynomial time unless the polynomial hierarchy collapses.The proof uses postselection gadgets to simulate PostBQP, though constructing inverses is complicated by postselection’s non-unitarity.

10.4 Classification of Reversible Classical Gates

The notes classify irreversible and reversible gate sets by the functions or permutations they generate, emphasizing ancilla assumptions, encoded universality, and the resulting inclusion structure.

  • Irreversible gates: AND and OR generate only monotone functions, while XOR generates only linear functions over F2 and cannot produce AND.
  • Encoded universality: {AND, OR} becomes universal under dual-rail encoding because swapping rails implements NOT and combining corresponding rails implements AND.The encoding represents 0 as 01 and 1 as 10.
  • Irreversible gates: Post’s classification gives seven possible function classes for irreversible gates when input-independent ancillas are available.The listed classes include AND-only, OR-only, XOR-only, NOT-only, and constant functions.
  • Ancilla assumptions: Dropping the assumption that 0 and 1 ancillas are freely available makes Post’s original lattice much more complicated.
  • Reversible gates: The reversible-gate classification extends the analysis toward quantum gate sets and is motivated by reversible computation’s role as a subset of unitary computation.The classification is presented as a necessary step toward classifying quantum gate sets.
  • Reversible gates: The reversible lattice places Toffoli at the top, identifies several encoded-universal nonlinear classes, and places CNOT-family computation within ⊕L.For prime k, adding any gate outside a Ck class reaches the full power of Toffoli; linear classes generated by CNOT, CNOTNOT, and CNOTNOT+NOT are not universal.
  • Reversible gates: With free classical ancillas returned to their initial states, the reversible classification simplifies to six sets: Toffoli, Fredkin, CNOT, T4, NOT, and the empty set.Allowing ancillas also removes permutation-sign difficulties that arise when only three-bit gates act on four bits.
Loading 1607.05256v1…