Source-linked AI summary
Quantum Algorithmic Measurement
Dorit Aharonov, Jordan Cotler, Xiao-Liang Qi
TL;DR
The paper asks how quantum computational resources can expand experimental capabilities and develops a complexity-theoretic framework for general quantum experiments. Using QUALMs, it studies experimentally motivated problems and finds exponential advantages from coherent access, while noting serious noise-resilience limitations.
Problem
The paper asks how to rigorously characterize the scope and limitations of using quantum computers to manipulate and measure physical systems.
Method
The authors define quantum algorithmic measurements (QUALMs), combining black-box quantum algorithms with interactive protocols to model general quantum experiments.
Results
For experimentally motivated tasks, coherent access QUALMs achieve an exponential complexity advantage over incoherent access, including against adaptive incoherent protocols.
Takeaways & Limitations
Quantum computers may provide exponential savings in resources for quantum experiments by enabling coherent use of experimental samples.
Takeaways & Limitations
The protocols lose their quantum advantage under local independent noise with any constant per-qubit noise probability p > 0 unless fault-tolerant encoding is used.
Abstract
from arXiv · showhide
We initiate the systematic study of experimental quantum physics from the perspective of computational complexity. To this end, we define the framework of quantum algorithmic measurements (QUALMs), a hybrid of black box quantum algorithms and interactive protocols. We use the QUALM framework to study two important experimental problems in quantum many-body physics: determining whether a system's Hamiltonian is time-independent or time-dependent, and determining the symmetry class of the dynamics of the system. We study abstractions of these problem and show for both cases that if the experimentalist can use her experimental samples coherently (in both space and time), a provable exponential speedup is achieved compared to the standard situation in which each experimental sample is accessed separately. Our work suggests that quantum computers can provide a new type of exponential advantage: exponential savings in resources in quantum experiments.
1 Introduction
The paper frames quantum experiments as computational processes and introduces QUALMs to quantify their complexity. It shows that coherent access can yield exponential advantages over incoherent access for experimentally motivated tasks, including fixed-unitary, non-unitarity, and symmetry-distinction problems.
- The quantum algorithmic measurement framework: QUALMs generalize quantum circuits to experiments by modeling hidden physical systems, laboratory interactions, and controlled workspace within a complexity-theoretic framework.The framework treats the Nature register as inaccessible, while the lab register mediates interaction with the working space.
- Exponential advantage from quantum coherence: The paper studies how much coherent access to experimental systems helps compared with incoherent access, including adaptive incoherent strategies.Coherent QUALMs permit arbitrary circuits on the lab and workspace registers, whereas incoherent QUALMs restrict operations and measure the lab after each oracle use.
- Exponential advantage from quantum coherence: Exponential lower bounds hold for incoherent adaptive QUALMs solving the fixed-unitary problem, while coherent access solves it with O(ℓ) complexity.The fixed-unitary result establishes an exponential separation even when incoherent protocols may adapt to earlier outcomes.
- Exponential advantage from quantum coherence: The fixed-state and non-unitarity problems likewise require exponential incoherent complexity but at most linear coherent complexity.For the fixed-state problem, the exponential lower bound applies in the unentangled adaptive setting; for non-unitarity, it applies to incoherent adaptive access.
- Exponential advantage from quantum coherence: The symmetry distinction problem also has an exponential lower bound for incoherent adaptive QUALMs, supporting entanglement-assisted symmetry discovery in a prototype setting.The paper presents symmetry measurement as experimentally relevant because symmetries are essential features of quantum many-body systems.
- Comparison with related results: The work reports the first exponential QUALM-complexity advantage for experimentally motivated tasks, achieved by a simple coherent protocol based on the SWAP test.The authors suggest this simplicity may help motivate experimental implementation, while noting that noise resilience remains unresolved.
2 QUALMs and Lab Oracles: Definitions
QUALMs formalize quantum experiments as circuits that interleave laboratory access to a physical system with admissible quantum operations. The framework represents experimental tasks as functions of lab oracles and specified inputs and outputs.
- Subsystems: The total system is H = N ⊗ L ⊗ W, where N is inaccessible Nature, L is the accessible lab, and W is the experimentalist’s working space.The subsystems contain n, ℓ, and w qubits, respectively.
- Lab oracles: A lab oracle is a pair LO = (E_NL, ρ_N), combining a quantum superoperator on the inaccessible Nature and accessible lab subsystems with Nature’s initial state.The experimentalist interrogates the Nature subsystem only through E_NL and processes the accessed information on L ⊗ W.
- Admissible operations: Admissible gates are quantum superoperators on L ⊗ W, and the allowed set can include arbitrary quantum operations or restricted operations such as classical processing.Measurements are included among superoperators, so the framework can represent different laboratory capabilities.
- Tasks: A task specifies input and output subsystems, a function f, and admissible gates G, and requires computing the experimental result using oracle calls and those gates.Tasks may map lab oracles and classical settings to classical outputs or probability distributions, including distinguishing tasks.
- QUALMs: A QUALM is an ordered sequence of admissible-gate symbols and oracle placeholders that compiles into a circuit by replacing each placeholder with the lab-oracle superoperator.The resulting circuit has designated input and output subsystems and intersperses experimental access with controlled quantum processing.
3 Exponential advantage for coherent access
This section establishes an exponential separation: coherent-access QUALMs distinguish fixed from freshly randomized Haar unitaries efficiently, whereas incoherent-access QUALMs require exponentially many queries, even with adaptivity.
- 3.1 Problem definition and statement of results: The task distinguishes a fixed Haar-random unitary from independent Haar-random unitaries, modeling time-translation-invariant versus stochastic dynamics.LOQℓ reuses one random unitary, while LO Pℓ applies a newly sampled random unitary on each call; the highly chaotic toy model assumes Haar randomness.
- 3.1 Problem definition and statement of results: O(ℓ) gate complexity and O(1) query complexity suffice for a coherent QUALM to distinguish LOPℓ from LOQℓ with error < 1/3.The construction uses a constant-query protocol whose gate cost is dominated by SWAP gates and Hadamards.
- 3.1 Problem definition and statement of results: A SWAP-test coherent QUALM always outputs 1 for LOQℓ, while Haar-state concentration makes its output differ for LOPℓ with constant bias.The probability that two Haar-random states have inner product below 1/100 is doubly exponentially close to 1 for sufficiently large ℓ, yielding probability greater than 1/3 for the relevant SWAP-test outcome.
- 3.3.3 The general incoherent access QUALM: The exponential separation persists against adaptive incoherent access: coherent lab-oracle access can be exponentially more efficient than incoherent adaptive access.The general incoherent QUALM is reduced to a mixture of simpler measurement QUALMs, whose output distributions remain exponentially close below the query threshold.
- 3.3.1 Simple measurement QUALM: The simple-measurement analysis already yields an exponential lower bound Ω(2^(ℓ/8)), although weaker than the general theorem’s bound.The reduction shows that a general incoherent QUALM would imply a simple measurement QUALM with the same distinguishing power and query complexity.
4 Corollaries
The paper derives corollaries extending the incoherent-access lower bound to correlated unitary ensembles, state ensembles, and non-unitarity detection. These results show that several oracle-distinction tasks remain difficult with limited incoherent access.
- 4.1 Correlated random unitaries: The unitary-ensemble corollary applies to distinguishing lab oracles whose sequences of unitaries are sampled from different left-invariant distributions.The distributions satisfy invariance under applying the same arbitrary unitary on the left to every sampled unitary.
- 4.1 Correlated random unitaries: Corollary 3 shows that lab oracles generated by distinct left-invariant unitary distributions are difficult to distinguish because both are close to the independently randomized oracle.The framework includes fixed and independently sampled unitaries as special cases of these distributions.
- 4.2 State ensembles: The state-ensemble setting includes distinguishing one repeatedly generated Haar-random state from independently regenerated Haar-random states.This is the state analogue of distinguishing fixed and independently sampled Haar-random unitaries.
- 4.2 State ensembles: Corollary 4 transfers the unitary-ensemble hardness result to distinct unitarily invariant state ensembles accessed through repeated state-preparation oracles.The reduction prepares a reference state before each oracle call and represents states through corresponding unitary ensembles.
- 4.3 Detecting non-unitarity: Corollary 5 relates non-unitarity detection to the earlier random-unitary problem by comparing a completely depolarizing oracle with a fixed-unitary oracle.For incoherent access, the depolarizing oracle has the same output behavior as the independently randomized-unitary oracle after averaging over random evolution.
5 QUALM for symmetry of time evolution operator
The paper formulates symmetry classification as distinguishing fixed Haar-random unitary, orthogonal, and symplectic lab oracles. Coherent access achieves this efficiently, whereas incoherent access requires exponentially many queries.
- Symmetry classes: Time-reversal with T^2 = 1 yields orthogonal dynamics, while T^2 = −1 yields symplectic dynamics and requires even Hilbert-space dimension.Without time-reversal symmetry, the dynamics belong to the unitary class.
- Problem definition: The task distinguishes fixed Haar-random elements of U(D), O(D), and Sp(D/2), representing different forms of time-reversal symmetry.The random matrix is selected once and reused on every oracle call.
- Main results: O(1) oracle queries and O(ℓ) gates suffice for coherent distinction among unitary, orthogonal, and symplectic dynamics.The coherent procedure is essentially a variation of the SWAP test and achieves constant bias.
- Main results: The incoherent-access query complexity for distinguishing the three symmetry classes is exponentially large, with a lower bound of Ω(2^(2ℓ/7)).This establishes an exponential query and QUALM-complexity gap between coherent and incoherent access.
- Coherent protocol: The coherent protocol prepares entanglement, applies the unknown unitary once, swaps registers, and measures a single-qubit signal whose distribution identifies the class.The preparation uses O(ℓ) gates, including Hadamards, CNOTs, and SWAP operations.
- Incoherent lower bound: A loop-graph construction maps pair partitions to unoriented loops, supporting the moment calculations used in the incoherent lower bound.The same procedure is applied in the symplectic case to obtain the corresponding upper bound on distinguishability quantities.
A Diagrams of quantum circuits and quantum channels
This appendix introduces diagrammatic notation for quantum circuits, channels, density matrices, subsystem wires, and indexed sums of superoperators. The notation makes matrix multiplication direction and subsystem structure explicit.
- Circuit notation: Directed wires encode matrix-multiplication order, with input and output indices represented by the wire orientation.A matrix M^β_α is drawn with an incoming α index and outgoing β index.
- States and channels: Density matrices use two wires because they have two indices, and pairs of oppositely oriented wires can be compressed into one thick wire.The same convention extends to sequences of applied unitaries and quantum channels.
- States and channels: A unitary channel acts as U[ρ] = UρU†, allowing channel notation to represent conjugation of density matrices compactly.The notation extends this construction to multiple applied unitaries.
- Subsystems: For composite Hilbert spaces, thick wires identify subsystems such as A and B, while channels act on their tensor-product state.The convention generalizes to any number of subsystems.
- Indexed channels: A dotted index labeled α denotes summation over matched collections of superoperators acting on separate subsystems.This notation represents channels built from paired operator families with a shared index set.
B QUALM example: verification of quantum computation
The QUALM framework expresses quantum-computation verification as an interaction between a classical verifier, a small controlled quantum register, and an honest-or-arbitrary quantum lab oracle. Existing protocols achieve polynomial QUALM complexity while maintaining correctness guarantees.
- Motivation and task: The verification problem asks how to check a quantum computation when classical simulation is exponential and the output cannot be directly checked.The task encodes a circuit U and input state |ψ0⟩, then produces a correct bit, an incorrect bit, or REJECT.
- Verification model: An almost-classical verifier controls O(1) qubits while interacting with a prover that may possess a quantum computer.The verifier otherwise uses polynomial classical computation and sends circuit instructions to the prover.
- Correctness guarantees: For an honest quantum prover, the protocol outputs the correct bit with probability at least 1 − ε; for any prover, incorrect output occurs with probability below ε.The latter guarantee allows REJECT as an alternative to an incorrect answer.
- QUALM encoding: The lab oracle models an honest quantum computer whose classical communication register stores gate instructions and whose superoperator applies them to the quantum register and controlled qubits.The lab consists of a polynomial-size classical channel, O(1) verifier-controlled qubits, and an n-qubit hidden register.
- Supported result: Verification of a general quantum computation can be achieved by a QUALM with polynomial QUALM complexity.This is the essence of the verification protocols cited in the paper, although fully classical access remains an open question.
C Review of unitary, orthogonal, and symplectic matrix integrals
This appendix reviews Haar integrals for unitary, orthogonal, and symplectic matrices and proves auxiliary lemmas used in the paper’s analyses.
C.1 Unitary matrix integrals
This section develops Haar unitary integrals through multi-index notation and Weingarten functions, expressing the latter as inverses of simpler matrices. It also states bounds and a large-dimension approximation for the unitary Weingarten function.
- C.1 Unitary matrix integrals: Unitary Haar integrals are written as sums over permutations, with Kronecker deltas contracting multi-indices and Weingarten weights depending only on permutation structure.The notation identifies complex conjugation, multi-indices, and conjugacy-class invariance of WgU.
- C.1 Unitary matrix integrals: WgU and the simpler matrix GU are inverses as k! × k! matrices, and their entries depend on permutation cycle structure.The associated distance |στ^-1| measures separation from the identity permutation.
- C.1 Unitary matrix integrals: |WgU(1, D) − D^-k| ≤ O(k^7/2 D^-(k+2)), giving a large-D approximation for the identity permutation.The bound is stated as Lemma 5 and follows directly from Eqn. (C.12).
- C.1 Unitary matrix integrals: The all-ones vector is an eigenvector of the relevant matrices, enabling computation of the eigenvalue needed for the Weingarten analysis.This follows because the matrix entries depend only on σ^-1τ.
C.2 Orthogonal matrix integrals
This section develops orthogonal matrix integrals using pair partitions, coset types, and orthogonal Weingarten functions. It derives moment formulas, inverse-matrix representations, and bounds sufficient for the paper’s purposes.
- C.2 Orthogonal matrix integrals: Pair partitions of {1, 2, ..., 2k} contain k pairs and number (2k − 1)!!, providing the combinatorial basis for orthogonal integrals.They are represented through P2(2k) and canonically mapped to M2k.
- C.2 Orthogonal matrix integrals: Coset types connect cycles containing paired elements, producing even connected-cycle lengths that are divided by two and reordered.Equivalent constructions are given using pairings in P2(2k) and permutations in M2k.
- C.2 Orthogonal matrix integrals: Orthogonal integrals contract paired indices according to pair partitions, with WgO depending only on the associated M2k cycle type.The reorganized formula uses combined multi-indices and traces of contraction operators.
- C.2 Orthogonal matrix integrals: For D > 12k^7/2, the orthogonal Weingarten function obeys a cycle-type-dependent bound that is slightly weaker than the unitary bound but sufficient here.The cited theorem applies to σm ∈ M2k, and the text states that this bound suffices for the intended analysis.
- C.2 Orthogonal matrix integrals: |WgO(σe, D) − D^-k| ≤ O(k^7 D^-(k+2)), giving the orthogonal analogue of the unitary identity-case estimate.This is stated as Lemma 7 and follows from Eqn. (C.37).
C.3 Symplectic matrix integrals
This section extends the orthogonal Weingarten framework to symplectic matrices by adding the symplectic form and related sign conventions. It presents symplectic moment formulas and bounds analogous to the unitary and orthogonal cases.
- C.3 Symplectic matrix integrals: The symplectic treatment follows the orthogonal case but additionally uses a D × D matrix representing the symplectic structure.The construction assumes D is even and uses the relation J^T = −J.
- C.3 Symplectic matrix integrals: Symplectic integrals are organized with multi-indices and contraction operators, including J⊗k factors inside the traced expressions.The resulting contractions pair indices while inserting the symplectic form between tensor powers.
- C.3 Symplectic matrix integrals: Using Eqn. (C.45), the section computes the first two nontrivial moments of the symplectic ensemble.The displayed expressions are stated to be obtained from the symplectic integration formula.
- C.3 Symplectic matrix integrals: The symplectic Weingarten bound applies for D > 6k^7/2 and uses the M2k cycle type, with |σm|Sp = |σm|O.The theorem is identified as Theorem 4.10 of [23].
- C.3 Symplectic matrix integrals: The symplectic Weingarten function is related to the orthogonal one through dimension and sign transformations involving the signature of σm.The derivation compares WgSp(τm, D/2) with WgO(τm, −D) and tracks parity-dependent signs.