Quantum Algorithmic Measurement

1.1 A computational complexity point of view on quantum experiments

• The paper initiates a complexity-theoretic study of quantum experiments by treating experiments as generalizations of quantum algorithms and analyzing their computational resources.The approach models experimental processes abstractly with quantum gates and circuits, extending computational-complexity methods to physical experiments.Source: §1 · p. 4, §1.1 · p. 4
• QUALM complexity counts admissible gates and lab-oracle applications, providing an implementation-independent measure of the resources needed for an experimental task.The framework hypothesizes that physical quantum experiments can be simulated by QUALMs with at most polynomial overhead, extending the quantum Church-Turing thesis to experiments.Source: §1.1 · p. 5, §1.2 · pp. 7–8

1.2 The quantum algorithmic measurement framework

• QUALMs model general quantum experiments as interactive protocols among hidden Nature, lab, and workspace registers, with unknown lab-oracle dynamics queried between admissible gates.The Nature register captures inaccessible degrees of freedom, while the lab register mediates interactions and the workspace contains controlled apparatus resources.Source: §1.2 · pp. 6–7
• A Task specifies the information extracted from lab oracles and laboratory constraints, while a QUALM is a gate-and-oracle sequence designed to achieve that task.A QUALM achieves a Task when its measured outputs match the Task function for every lab oracle and input string, exactly or approximately.Source: §1.2 · pp. 6–7

1.3 Exponential advantage from quantum coherence

• The framework compares unrestricted QUALMs, which coherently manipulate L and W, with incoherent QUALMs restricted to local operations, classical communication, and measurements after each oracle use.Incoherent access prevents coherent quantum information from surviving for subsequent interactions with the lab oracle.Source: §1.3 · pp. 8, 10
• The fixed unitary problem distinguishes an oracle that repeatedly applies one remembered random unitary from an oracle that applies a fresh random unitary at every call.The problem serves as a toy model for distinguishing time-independent Floquet evolution from generically time-dependent dynamics.Source: §1.3 · p. 10
• The incoherent lower bound for adaptive protocols requires Weingarten functions and substantial combinatorial analysis, whereas the coherent upper bound follows from a simple entanglement-based protocol.The result reflects that deterministic, time-translation-invariant dynamics can emulate stochastic dynamics despite their differing physical descriptions.Source: §1.3 · p. 11
• Coherent access QUALMs can be exponentially more efficient than incoherent adaptive QUALMs for the fixed unitary problem.The coherent protocol has complexity O(ℓ), while every incoherent protocol requires complexity exponential in ℓ; the coherent procedure can use a simple SWAP test.Source: §1.3 · p. 11
• Exponential QUALM separations hold for fixed-state, non-unitarity, and symmetry-distinction problems: incoherent adaptive access is exponentially costly, whereas coherent access is at most linear for the first two and uses the SWAP test for symmetry.The symmetry lower bound remains exponential even with adaptive incoherent strategies, while the coherent protocol requires at most a linear number of gates.Source: §1.3 · pp. 11–12

1.6 Comments and open questions

• The results depend on idealized Haar-random, highly nonlocal unitaries: unitary designs preserve the proofs for polynomially many queries, but noise, physical implementation, and scalable realization remain unresolved.Constant local noise destroys the SWAP-test advantage, while fault-tolerant encoding preserves it only under an extremely nonphysical oracle choice; implementing QUALM interactions experimentally is also challenging.Source: §1.3 · pp. 12–13, §1.6 · pp. 19–20

1.4 Comparison with related results

• Compared with related algorithms, this advantage extends beyond query complexity because prior protocols such as [11] and [57] use exponential-gate coherent procedures, while communication-complexity savings do not generally reduce full QUALM complexity.Simon’s algorithm is classified as local-local rather than a coherent-versus-incoherent separation, and Hidden Subgroup advantages remain conjectural or gate-inefficient in the relevant sense.Source: §1.4 · pp. 15–16
• These results are the first exponential coherent-versus-incoherent QUALM advantage for experimentally motivated tasks, achieved by a simple SWAP-test protocol even against adaptive incoherent access.The work argues that entanglement can reveal physical symmetries using exponentially fewer resources than conventional methods.Source: §1.3 · p. 12, §1.4 · p. 16

1.5 Related models

• QUALMs generalize quantum circuits and interactive protocols for experiments by modeling indirect system access, hidden memory, and interactions between the physical system and experimental workspace.The framework relates to quantum oracle algorithms, quantum strategies, combs, process tensors, and superdensity operators, while retaining an interactive Nature register.Source: §1.5 · pp. 17–18

1.6 Comments and open questions

• Open questions include whether adaptiveness or weaker intermediate measurements yield further separations, whether more physical lab oracles support them, and how QUALM descriptions translate into experimental gates and oracle calls.The supplementary material then organizes definitions in Section 2, fixed-unitary results in Sections 3–4, symmetry distinction in Section 5, and technical background in the appendices.Source: §1.6 · pp. 19–20, §1.7 · p. 21

2.2 Quantum Algorithmic Measurements

• A lab oracle is a pair LO = (E_NL, ρ_N), where E_NL is a CPTP map on N ⊗ L and ρ_N is a state on N.The experimentalist controls L ⊗ W, interrogates N only through E_NL, and processes the accessed information using admissible operations.Source: §2.2 · p. 22
• A QUALM is an ordered quantum circuit over admissible gates with designated slots for lab-oracle calls, input subsystem S_in, and output subsystem S_out, implementing a task on lab oracles and inputs.Tasks specify S_in, S_out, a function f, and admissible gate set G; the framework also allows probabilistic outputs and quantum input or output states.Source: §2.2 · pp. 22, 24, 25

2.3 QUALM complexity

• QUALM complexity separates gate complexity from query complexity and defines exact task complexity by minimizing their sum over QUALMs implementing the task.Gate complexity counts admissible-gate symbols, query complexity counts lab-oracle slots, and the two measures can trade off when their sum is minimized.Source: §2.3 · pp. 26–27

2.4 Different types of access to a lab oracle

• The framework distinguishes coherent access, allowing a general QUALM with a universal gate set, from incoherent access, which models experimental restrictions through constrained gates and sequences such as one-round LOCC protocols.Coherent access is the full-quantum-computer model, whereas realistic experiments may lack entanglement between N ⊗ L and W or lose system coherence through measurement.Source: §2.4 · p. 28
• Incoherent QUALMs require LOCC interaction between lab and working registers, with a complete measurement of the lab register between every two oracle applications.This prevents coherence between states produced by separate oracle calls, although the protocol may adapt future lab inputs to earlier measurement outcomes.Source: §2.4 · p. 29
• Incoherent access still permits adaptive oracle use, because the lab register’s next input may depend on previous measurements of both lab and working registers.Source: §2.4 · p. 29

2.5 Examples of Quantum Tasks

• QUALMs subsume ordinary quantum algorithms by taking trivial nature and lab registers, a trivial oracle, and a universal gate set to compute f.Source: §2.5 · pp. 29–30
• Quantum state tomography is modeled by an oracle that replaces the lab register with ρ, requiring an output state from an epsilon net within ϵ in trace norm.A deterministic partition formulation is non-physical because arbitrarily close states can receive different outputs, so a probabilistic function provides approximation ϵ with error δ.Source: §2.5 · p. 30
• Quantum cooling tasks use lab oracles that prepare Gibbs states ρk(T) and ask the QUALM to output the state cooled to 1/s of its initial temperature without Hamiltonian access.An efficient QUALM is known for the weaker task of estimating local-observable expectations at the reduced temperature.Source: §2.5 · p. 31
• Quantum communication is represented with separated Alice and Bob workspaces connected by a swap lab oracle, making QUALM query complexity equal quantum communication complexity asymptotically.The construction counts a bit swap as one operation, creating only a factor-of-two mismatch with standard directional qubit counting [94].Source: §2.5 · p. 32
• The framework also accommodates control and imaging: lab-oracle interactions expose properties or dynamics of Nature, whose processed signals become control decisions or output images.The section states that, to the authors’ knowledge, all cited quantum experiments can be cast as QUALMs; related control-theory work is cited in [31].Source: §2.5 · pp. 32–33

3.1 Problem definition and statement of results

• The task distinguishes many copies of one fixed Haar-random unitary from many independently sampled Haar-random unitaries, modeling time-translation-invariant versus stochastic dynamics.The fixed-unitary case represents a Floquet system, while independently resampled unitaries represent time-dependent stochastic evolution; the coherent protocol uses a SWAP test and constant-query amplification.Source: §3.1 · pp. 33–37
• Coherent access distinguishes LOPℓ from LOQℓ with error < 1/3 using O(ℓ) gates and O(1) queries, whereas incoherent access requires Ω(22ℓ/7) queries.The incoherent output states have trace distance O(k3/2ℓ) and bias at most δ = O(k3/2ℓ) for k below the theorem’s threshold; together, the theorems establish an exponential advantage even against adaptive incoherent access.Source: §3.1 · pp. 36–37

3.2 Proof of a restricted case of Theorem 4: the parallel repetition case

• For any choice of ℓ-qubit unitaries V and Y, the total variational distance is O(k22−ℓ/4), and the resulting QUALM complexity lower bound is Ω(2ℓ/8), which is exponential.Qk is flat on no-collision ℓ·k-bit strings and has collision probability at most ϵQ ≤2k22−ℓ/4.Source: §3.2 · pp. 38, 40
• Haar-randomness is essential: negligible collision probability alone does not imply hardness, whereas the random unitary leaves enough randomness to defeat any fixed distinguishing rule.A fixed subset distribution can be distinguished with O(1) samples despite negligible collision probability, because it does not satisfy the required total-variation closeness.Source: §3.2 · p. 41

3.3 Proof of Theorem 4

• Theorem 4 follows by showing that simple-measurement QUALMs cannot distinguish LOP_ℓ from LOQ_ℓ, then reducing general incoherent-access QUALMs to probabilistic averages of simple-measurement QUALMs.The proof combines the restricted simple-measurement case with a reduction for general incoherent access.Source: §3.3 · p. 41, §3.3.1 · p. 44

3.3.1 Simple measurement QUALM

• A simple-measurement QUALM records each rank-one POVM outcome in a fresh tensor factor, prepares a possibly adaptive state, and applies a final readout channel to the recorded distribution.The measurement basis and prepared state may depend on previous outcomes, and the reduced laboratory channel is a measure-and-prepare channel.Source: §3.3.1 · pp. 41, 43
• Lemma 3 establishes that the outcome distributions Q_k and P_k for LOQ_ℓ and LOP_ℓ are difficult to distinguish, yielding the restricted Theorem 4 result for simple-measurement QUALMs.The proof bounds their 1-norm distance using Haar integration and Weingarten-function expansions.Source: §3.3.1 · p. 44, §3.3.2 · pp. 45–46

3.3.2 Proof of Lemma 3

• The Lemma 3 proof separates the identity permutation from nontrivial permutations and bounds the latter through cycle lengths, adaptive-index dependencies, and red-blue segment suppression factors.Each segment contributes dimension-dependent suppression, and the resulting bound is controlled by the net red and blue segment lengths.Source: §3.3.2 · pp. 45, 46, 49

3.3.3 The general incoherent access QUALM

• Claim 2 derandomizes every incoherent-access QUALM into a probability distribution over simple measurement QUALMs with identical query complexity and oracle-independent weights.For every lab oracle, the original output distribution is the weighted average of the derived simple measurement outputs.Source: §3.3.3 · p. 51
• Any incoherent-access QUALM distinguishing the target lab oracles with error below 1/3 would imply a same-query simple measurement QUALM, which is impossible below order 22ℓ/7.Below this query complexity, the simple measurement QUALM output distributions are exponentially close in ℓ.Source: §3.3.3 · p. 51
• The proof separates oracle-dependent and oracle-independent conditional probabilities: W-to-L instructions are oracle-independent, while complete measurements make each L-to-W probability depend only on the intervening oracle application.The post-measurement state is fixed by the measured vector, removing dependence on earlier oracle applications.Source: §3.3.3 · pp. 54–55
• Oracle-independent probabilistic instructions are represented using independent random variables and deterministic functions, yielding fixed-randomness QUALMs whose oracle-dependent distributions can be compared directly.Each fixed choice of random bits specifies deterministic functions for the relevant measurement and communication indices.Source: §3.3.3 · pp. 55–56
• A sequence of weak measurements followed by a projective measurement is converted into one generalized projective measurement by adding an auxiliary system, making the fixed-randomness QUALM a simple measurement QUALM.The resulting simple-measurement distribution contains auxiliary variables whose omission can only reduce distinguishability.Source: §3.3.3 · pp. 57–59
• The proof bounds the bias of a general incoherent-access QUALM with k rounds of lab-oracle applications using Lemma 3 and Eqs. (3.58) and (3.78).The passage identifies the right-hand side as the bias for the simple-measurement QUALM and states that these bounds yield the conclusion.Source: §3.3.3 · p. 59
• The resulting argument proves Theorem 4.Source: §3.3.3 · p. 59

4 Corollaries

• The section presents three corollaries of Theorem 4 covering elaborate unitary ensembles, state ensembles, and random-unitary versus completely depolarizing-channel distinction.The results concern tomography-themed quantum tasks and QUALMs.Source: §4 · p. 59

4.1 Correlated random unitaries

• Corollary 3 shows that lab oracles generated by different left-invariant unitary distributions are difficult to distinguish with incoherent access because both are close to independent-random-unitary access.The framework includes independently sampled and perfectly correlated unitaries; implementation uses a query-count register.Source: §4.1 · p. 60

4.2 State ensemble distinction

• Corollary 4 bounds an incoherent QUALM’s distinguishing bias between two unitarily invariant state-ensemble distributions by O(k3/2ℓ) under the stated query condition.The reduction represents each state ensemble using unitaries applied to a reference state, then invokes Corollary 3.Source: §4.2 · p. 61

4.3 Detecting non-unitarity

• Corollary 5 states that an incoherent QUALM cannot distinguish a completely depolarizing-channel oracle from a fixed-unitary oracle with bias bigger than O under the stated query condition.Averaging random unitary evolution yields the completely depolarizing channel, reducing the problem to the independent-random-unitary case.Source: §4.3 · p. 62

5.1 Outline of problem

• The task distinguishes fixed Haar-random elements of U(D), O(D), and Sp(D/2), representing absent time-reversal symmetry or one of two symmetric classes with T^2 = ±1.The symplectic class requires even Hilbert-space dimension.Source: §5.1 · pp. 62–63

5.2 Problem definition: distinguishing between symmetries of unitaries

• Coherent access distinguishes the three symmetry classes with O(1) oracle queries and O(ℓ) gates, whereas incoherent access requires e^Ω(ℓ) queries and gates.This establishes an exponential gap in query and QUALM complexity for determining the type of time-reversal symmetry.Source: §5.1 · p. 63

5.4 Proof of Theorem 6

• The incoherent lower bound shows that, below the stated exponential query threshold, the three output distributions remain pairwise exponentially close in total variation distance.The proof extends the simple-measurement argument to full incoherent QUALMs using Claim 2 and orthogonal and symplectic Weingarten-function estimates.Source: §5.2 · p. 65, §5.4 · p. 69

5.3 Proof of Theorem 5

• The coherent QUALM uses a SWAP-test variation with two oracle queries, controlled swaps, and an additional J transformation to separate orthogonal, unitary, and symplectic cases.For the matching symmetry class, the |+⟩ outcome occurs with probability one, while the other relevant cases yield |+⟩ and |−⟩ probabilities exponentially close to 1/2.Source: §5.3 · pp. 65, 67, 68

5.4 Proof of Theorem 6

• For orthogonal and symplectic cases, pair partitions are mapped to unoriented loops, whose nontrivial-loop contributions reduce to products of state overlaps, with complex conjugation preserving orthonormality.The same loop procedure yields the corresponding upper bound in the symplectic case.Source: §5.4 · pp. 75–76
• Theorem 6 follows by combining bounds on the c1, c2, and T terms obtained from Weingarten-function estimates and Cauchy–Schwarz arguments.The derivation applies standard Weingarten bounds in the unitary, orthogonal, and symplectic cases, under the stated restrictions on k and D.Source: §5.4 · pp. 73, 74, 76
• Claim 2 upgrades the simple-measurement QUALM result of Lemma 4 to the incoherent-access QUALM setting of Theorem 6.This completes the proof after the preceding bounds are established.Source: §5.4 · p. 76

A Diagrams of quantum circuits and quantum channels

• Directed circuit wires indicate matrix-multiplication order, with box in- and out-lines corresponding to matrix indices.A matrix M^β_α is represented by a box whose in-line carries α and out-line carries β; the notation extends to arbitrary sequences of unitaries.Source: A Diagrams of quantum circuits and… · p. 77
• Density matrices use two wires, while unitary channels U_k[ρ] = U_kρU†_k use two input and two output wires.The channel notation simplifies the representation of conjugation by a unitary and generalizes to arbitrary superoperators.Source: A Diagrams of quantum circuits and… · p. 77
• Pairs of oppositely oriented wires are compressed into a single thick wire, forming the paper’s primary notation for superoperator diagrams.This thick-wire notation represents the action of arbitrary superoperators S1, S2, ... .Source: A Diagrams of quantum circuits and… · p. 78
• For multipartite Hilbert spaces, each thick wire denotes one subsystem, so channels acting on N subsystems produce N thick wires.For H ≃ A ⊗ B, channels acting on ρ_A ⊗ ρ_B are depicted with one thick line for each subsystem.Source: A Diagrams of quantum circuits and… · pp. 78–79
• A dotted line labeled α denotes summation over a shared index when paired superoperator collections act jointly across subsystems.The construction combines {S_α} acting on A with {S′_α} acting on B through a channel on states ρ_AB.Source: A Diagrams of quantum circuits and… · p. 79

Verification protocol

• Almost classical protocols use a polynomial-power classical verifier with a fully controlled quantum computer of one or a few qubits to verify a prover’s computation [4] [16].The verifier interacts with a potentially quantum prover and seeks a specified output bit without trusting the prover.Source: B QUALM example: verification of… · p. 80

Verification guarantees

• A valid protocol outputs the correct bit with probability at least 1 − ε for an honest prover and outputs an incorrect bit with probability below ε for any prover.For arbitrary provers, the protocol may instead output REJECT.Source: B QUALM example: verification of… · p. 80

QUALM formalization

• The honestQC lab oracle models a quantum computer by applying classically specified gates to an n-qubit register together with the verifier’s small quantum register.The formal model separates a classical communication channel, a few controlled qubits, and polynomial-size classical workspace.Source: B QUALM example: verification of… · p. 80
• The QUALM task encodes a polynomial-size circuit U and computational-basis input |ψ0⟩, then produces 0, 1, or REJECT in a two-qubit output register.The input description occupies a k = O(poly(n)) subsystem of the verifier’s classical working register.Source: B QUALM example: verification of… · pp. 80–81

QUALM result

• Polynomial QUALM complexity achieves verification of a quantum computation, while whether this remains possible with an entirely classical lab is a major open question.This result captures the essence of verification protocols in [4] [16].Source: B QUALM example: verification of… · p. 81

C Review of unitary, orthogonal, and symplectic matrix integrals

• The section reviews facts about Haar unitary matrix integrals.Source: C Review of unitary, orthogonal, and… · p. 81
• It also reviews facts about Haar orthogonal matrix integrals.Source: C Review of unitary, orthogonal, and… · p. 81
• The review covers Haar symplectic matrix integrals and proves useful lemmas, drawing largely on [23] [73].Source: C Review of unitary, orthogonal, and… · p. 81

Unitary matrix integrals

• Haar unitary integrals are expressed using multi-indices and Weingarten functions, with conjugation represented by barred matrix elements.The notation IJ denotes products of k matrix elements, while the barred factors are complex conjugates.Source: §C.1 · p. 81
• The Weingarten function depends only on permutation conjugacy classes and is invariant under inversion and related permutation rearrangements.These symmetries support treating WgU and the associated matrix representations through permutation classes.Source: §C.1 · p. 82
• Weingarten functions are inverses of a simpler k! × k! matrix whose entries are determined by permutation cycle counts and distances from the identity.The associated matrices GU and WgU are symmetric inverses.Source: §C.1 · p. 82
• Lemma 5 states |WgU(1, D) − D^-k| ≤ O(k^7/2 D^-(k+2)).The proof follows directly from Eqn. (C.12).Source: §C.1 · p. 83

Pair partitions

• Pair partitions of {1, ..., 2k} contain (2k)!/(2^k k!) = (2k − 1)!! elements and can be represented canonically as elements of M2k.The representation uses ordered pairs and increasing first elements, with a natural M2k action on pair partitions.Source: §C.2 · pp. 83–84

Weingarten calculus

• Orthogonal matrix integrals are reorganized over pair partitions and their canonical M2k representatives, with contractions indexed by pairings and multi-indices reduced from length 2k to k.The resulting formulation parallels the unitary case and uses pairwise contractions encoded by the pairing operators.Source: §C.2 · p. 85

Orthogonal ensemble moments

• The first two nontrivial moments of the orthogonal ensemble follow from the reorganized Weingarten formula, while WgO is identified as the inverse of the pairing matrix GO.The inverse relation is established through a (2k − 1)!! × (2k − 1)!! matrix indexed by pairings.Source: §C.2 · p. 86

Bounds

• For D > 12k^7/2, the orthogonal Weingarten function satisfies a cycle-type-dependent bound that is slightly weaker than the unitary bound but sufficient here.A corresponding estimate gives |WgO(σe, D) − D^-k| ≤ O(k^7D^-(k+2)).Source: §C.2 · p. 86

• The symplectic treatment introduces a D × D matrix J satisfying J^T = −J, with D even and 0_{D/2} the all-zero D/2 × D/2 matrix.Source: §C.3 · p. 87
• Symplectic contractions are computed by inserting J^⊗k between paired tensor factors, with analogous expressions for the corresponding trace quantity.Source: §C.3 · p. 88
• Using Eqn. (C.45), the section derives the first two nontrivial moments of the symplectic ensemble.Source: §C.3 · p. 88
• For σ_m ∈ M_{2k} and D > 6k^{7/2}, Theorem 4.10 of [23] supplies a symplectic bound indexed by σ_m’s M_{2k}-cycle type, with |σ_m|_{Sp} = |σ_m|_O.Source: §C.3 · p. 88
• The symplectic Weingarten function is related to the orthogonal one through |Wg_{Sp}(τ_m, D/2)| = |Wg_O(τ_m, −D)|, with asymptotic sign factors determining positivity.Source: §C.3 · p. 89