Quantum Pseudorandomness and Classical Complexity

1 Introduction

• Recent work extends computational pseudorandomness to quantum states and unitaries that resemble the Haar measure.These objects are intended to appear random to computationally bounded adversaries.Source: §1 · p. 1
• PRS ensembles are efficiently generated keyed quantum states indistinguishable from Haar-random states, while PRUs are efficiently implementable unitaries indistinguishable from the Haar measure.The definitions are quantum analogues of pseudorandom generators and pseudorandom functions, respectively.Source: §1 · p. 1
• Quantum pseudorandom states and unitaries can make Haar-measure approximations more efficient than t-designs and support a range of cryptographic primitives.The cited applications include quantum money, commitments, multiparty communication, signatures, and symmetric-key encryption.Source: §1 · p. 1

1.1 Main results

• QMA’s classical-input formulation does not by itself establish an efficient way to break PRSs, whose adversary operates on quantum inputs.The apparent QMA attack uses a classical circuit description as a witness, but the input-type distinction leaves the complexity connection unclear.Source: §1.1 · p. 2
• A polynomial-time quantum algorithm with a PP oracle can distinguish pseudorandom states from Haar-random states, so PRSs do not exist if BQP = PP.This addresses whether a computational complexity assumption is needed for PRSs.Source: §1.1 · p. 2
• A quantum oracle O exists relative to which BQP = QMA and PRUs, hence PRSs, exist.The stronger promise-problem equality PromiseBQPO = PromiseQMAO also holds.Source: §1.1 · p. 2
• The quantum-oracle construction separates PRUs from nontrivial quantum-secure classical cryptography, giving a relativized negative answer to whether quantum-secure one-way functions are necessary for PRSs.The theorem’s result contrasts with the absence of computationally secure classical cryptography when BQP = QMA.Source: §1.1 · pp. 2–3
• The result suggests that quantum cryptography may be possible under weaker assumptions than classical cryptography, and motivated later constructions from pseudorandom states and unitaries.The cited later works appeared after this work was originally published.Source: §1.1 · p. 3

1.2 Application: hyperefficient shadow tomography

• Hyperefficient shadow tomography estimates all listed measurement expectations through an implicitly represented circuit in time polynomial in n, log M, and 1/ε.The input includes an algorithm implementing each measurement, and the circuit approximates Tr(O_iρ) for each i.Source: §1.2 · p. 3
• The paper places this result alongside earlier evidence that hyperefficient tomography is unlikely, including an oracle separation concerning quantum versus classical advice.The earlier separation applies when observables are given as black-box measurements.Source: §1.2 · p. 3
• If hyperefficient tomography works for rank-one observables supplied through state-preparation access, then every PRS ensemble can be broken by polynomial-time quantum adversaries with a PromiseQCMA oracle.The PRS generator supplies state preparation for the corresponding observable list.Source: §1.2 · p. 4
• Hyperefficient shadow tomography is impossible with black-box state-preparation access to observables, given the paper’s oracle where BQP, QCMA, and QMA coincide and PRSs exist.The implication follows because such tomography would allow PRSs to be broken with a PromiseQCMA oracle.Source: §1.2 · p. 4

1.3.1 Approximate t-designs

• Approximate t-designs support replacing Haar measure in quantum query analyses when substitution preserves acceptance probability up to relative error.The paper formalizes t-design properties in this setting and notes that related assumptions had previously been used without proof.Source: §1.3.1 · p. 4

1.3.2 Breaking pseudorandomness with PP

• Random Clifford measurements reveal whether an unknown state is close to a member of a PRS ensemble, and Bayesian decision on their outcomes is at least as effective as any other decision rule.Postselection approximates the posterior probabilities; PostBQP = PP then gives the PP-oracle simulation, with an approximate design replacing inaccessible Haar-state preparation.Source: §1.3.2 · p. 5

1.3.3 Instantiating pseudorandomness with BQP = QMA

• The constructed oracle combines Haar-random unitary families with an independently built classical language, and its PRU security proof uses Grover-query optimality.The security argument is independent of the classical language’s choice so long as it is independent of the sampled unitaries.Source: §1.3.3 · p. 5
• To establish BQPU,C = QMAU,C, the proof handles small unitaries by learning them and large unitaries by Haar concentration, then uses C to return acceptance-probability approximations.For large n relative to the verifier’s query count, the verifier’s maximum acceptance probability is close to its Haar-averaged value.Source: §1.3.3 · p. 6

1.4 Open problems

• Whether classical oracles can yield similar PRS or PRU separations remains open, with unitary synthesis and QMA security posing obstacles.The authors note that an existing random-oracle PRS construction can be broken with an NP oracle, while a weaker single-copy-secure construction exists relative to an oracle with P = NP.Source: §1.4 · p. 6
• Quantum minimum circuit size asks for the smallest circuit that approximately prepares a given state from copies, and may be hard if PRSs exist.The authors connect this question to quantum meta-complexity and note its relevance to the wormhole growth paradox and Complexity=Volume conjecture.Source: §1.4 · p. 6
• The authors ask whether random local-gate circuits are computationally pseudorandom, beyond their known role as approximate unitary designs.They also ask for candidate PRS and PRU constructions that do not rely on BQP ≠ QMA.Source: §1.4 · p. 7

1.5 Conference version

• The paper adds a new section on t-designs compared with the conference version.The addition is Section 3.Source: §1.5 · p. 7
• The revised oracle keeps the quantum component U but replaces the conference version’s arbitrary PSPACE-complete classical oracle with a specific recursively constructed language.Source: §1.5 · p. 7
• The oracle changed after an error was discovered in the proof, and the paper discusses the error and prospects for restoring the earlier construction.Source: §1.5 · p. 7

2.1 Basic notation

• Basic notation fixes conventions for binary strings, finite sets, sampling, negligible functions, and polynomial bounds.Source: §2.1 · p. 7

2.2 Probability

• The probability preliminaries state the optimality of the Bayes decision rule and the Borel–Cantelli criterion for finitely many events occurring almost surely.Source: §2.2 · p. 7

2.3 Quantum information

• Quantum-information conventions include trace and diamond distance, superoperator ordering, and a bound relating unitary-channel diamond distance to matrix Frobenius distance.The bound is at most twice the Frobenius distance between the unitaries.Source: §2.3 · p. 8

2.4 Haar measure and concentration

• The Haar-measure preliminaries define the relevant state and unitary distributions and state a concentration inequality for Lipschitz functions on products of unitary groups.Source: §2.4 · p. 9

2.5 Complexity theory

• The complexity preliminaries define BQP, QMA, and PostBQP for promise problems and specify a reasonable algebraic-entry gate-set assumption for PostBQP.Source: §2.5 · p. 10

2.6 Quantum oracles

• In the quantum-oracle model, polynomial-time machines may query sequence member U_n at cost n, with queries allowing U_n, its inverse, or controlled versions.The model also includes classical oracles as a special case.Source: §2.6 · p. 11

2.7 Cryptography

• The cryptographic preliminaries define PRSs and PRUs through efficient generation or implementation and indistinguishability against quantum adversaries.The paper considers ensembles with n(κ) = ω(log κ), non-uniform quantum adversaries with classical advice, and PRS security for every polynomial number of copies.Source: §2.7 · p. 11

3 Approximate t-designs

• Approximate state and unitary t-designs approximate the first t Haar moments with multiplicative 1 ± ε error, and unitary designs induce state designs.Applying a unitary design to any fixed state gives an approximate quantum t-design.Source: §3 · p. 12
• Approximate designs can replace Haar randomness in algorithms using t state copies or parallel unitary queries, changing measurement probabilities by at most a small multiplicative factor.Source: §3 · p. 13
• Adaptive queries to U without controlled-U or U† can be simulated using Choi states, gate teleportation, and postselection, extending the parallel-query design bound.Each simulated query succeeds with probability 1/N^2, so all t postselections succeed with probability 1/N^(2t).Source: §3 · pp. 14–15
• The adaptive-query extension does not establish the corresponding result for algorithms querying both U and U†; the authors identify this as an open question.They note that the simulation does work for real orthogonal matrices because Uᵀ = U†.Source: §3 · p. 15
• Controlled-U queries are handled by requiring phase-invariant unitary designs and choosing the phase of U randomly.The design can be made phase-invariant by multiplying each unitary by a uniformly random (t + 1)th root of unity.Source: §3 · pp. 15–16
• The controlled-query argument constructs a phase-averaged Choi-state mixture from t copies of the Choi state of U, enabling the design comparison.The construction uses the fact that the first t moments of the selected roots of unity match those of uniform complex phases.Source: §3 · pp. 16–17

• The algorithm measures each input copy in an independently random Clifford basis, then sends the bases and outcomes to a PP language defined via PromisePostBQP.Source: §4 · p. 18
• For pseudorandom input, some key projector has overlap 1, whereas for Haar-random input every key overlap is below 1/3 except with negligible probability when n = ω(log κ).Source: §4 · p. 19
• With T = poly(κ) copies, a poly(κ)-time quantum algorithm using one PP-language query distinguishes PRS from Haar-random states with probability at least 0.999.Source: §4 · pp. 18–19
• The classifier tests whether any key projector’s estimated overlap reaches 2/3, identifying the ensemble with probability at least 0.999.Source: §4 · p. 19
• The result also holds relative to all oracles when the PRS generator queries a classical or quantum oracle, using a PromisePostBQPU distinguisher.Source: §4 · p. 20

5.1 Definition of the oracle

• The constructed oracle pairs a sequence of direct-sum Haar-random unitaries U with a deterministic classical language C defined in stages.C’s definition uses verifier descriptions and averages acceptance over the sampled unitary distribution; the verifier’s length bound ensures the definition is not circular.Source: §5 · p. 20, §5.1 · pp. 20–21

5.2 PromiseBQP = PromiseQMA relative to (U, C)

• With probability 1 over the constructed oracle, PromiseBQP and PromiseQMA coincide.The classical oracle encodes average acceptance tests for QMA verifiers, while the proof uses unitary estimation and Lipschitz acceptance probabilities.Source: §5.2 · pp. 21, 23

5.3 Pseudorandom unitaries relative to (U, C)

• For any fixed language C, with probability 1 over U, there exists a family of PRUs relative to (U, C) whose parameter satisfies n(κ) = κ.An extension to adversaries with quantum advice is left to future work.Source: §5.3 · p. 25

5.4 Alternative oracles

• An earlier version [Kre21a] had a flawed proof of PromiseBQP = PromiseQMA relative to an oracle using a PSPACE-complete language; the authors conjecture that equality nevertheless holds.The earlier oracle still supports PRUs, since the PRU result applies regardless of the fixed classical language.Source: §5.4 · pp. 25–26
• Proposition 35 [Aar09, Lemma 4] represents a T-query verifier’s acceptance probability using a degree-2T matrix polynomial, whose sufficiently high power-trace estimates p(O).The text says k can be chosen sufficiently large, for example 100m, to provide an arbitrarily precise estimate.Source: §5.4 · p. 26
• The proposed PSPACE route is to average Tr(M(U, P)^k), a degree-2Tk polynomial with PSPACE-computable coefficients, over Haar measure.The coefficients are said to be computable by standard path-integral techniques [NC10, Section 4.5.5]; the text presents PSPACE averaging as a possibility.Source: §5.4 · p. 26
• They propose Haar integration via Weingarten calculus [CMN22] or sufficiently strong unitary t-designs, but forward-query verifiers still induce both U and U†, obstructing Lemma 25.The text says Lemma 25 does not seem applicable to this expression.Source: §5.4 · p. 27

A PRSs with Binary Phases

• The construction by Ji, Liu, and Song, shown secure by Brakerski and Shmueli [BS19], is based on pseudorandom functions.The section sketches how this construction can be broken efficiently with an NP oracle.Source: A PRSs with Binary Phases · p. 31
• The procedure samples uniformly random pairs (x, y) satisfying fk(x) = fk(y).A computational-basis measurement yields |0⟩|x⟩|y⟩ with nonzero probability exactly when the PRF outputs coincide.Source: A PRSs with Binary Phases · p. 31
• With sufficiently many samples, an NP language accepts PRF-based pseudorandom states and accepts Haar-random states only with negligible probability.It tests whether some key makes every sampled pair satisfy fk(xi) = fk(yi).Source: A PRSs with Binary Phases · p. 31
• The procedure still works with good probability when each PRF is close to balanced, as PRF families must be to avoid efficient distinction from random functions.Closeness here means that only a negligible fraction of outputs need changing to make the function balanced.Source: A PRSs with Binary Phases · p. 31