Quantum Advantage has Few Complexity Implications

Alex Lombardi; Eli Goldin; Tomoyuki Morimae

REVIEW

Quantum Advantage has Few Complexity Implications

Eli Goldin, Alex Lombardi, Tomoyuki Morimae

Quantum Physics · Submitted 3 Nov 2026 · 58 references

Pith's verdict: A serious relativization result: if the LLM-originated core of Theorem 4.12 holds up under human re-verification, this paper settles the relativized forms of Conjectures 1.1 and 1.2 and deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 4, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2611.05303 (version 1)

Pith IDJF2W6DCI, Pith's permanent record of this paper and its review

CitationAlex Lombardi, Eli Goldin, Tomoyuki Morimae. "Quantum Advantage has Few Complexity Implications." arXiv:2611.05303 (2026). https://pith.science/paper/JF2W6DCI

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The thing to know: this is the strongest relativization barrier for proofs of quantumness and qv-OSP that I have seen. If Theorem 4.12 holds, the paper settles the relativized forms of Conjectures 1.1 and 1.2, gives a classical oracle with P = NP, BQP = PSPACE, and an IP language hard for P/poly, plus PoQ and qv-PoQ; and a unitary oracle with BQP = QCMA and qv-OSP. The corollaries blocking relativizing cryptography, round reduction, and CVQC from these primitives follow cleanly.

What is genuinely new is the oracle design: A is a multilinear-extension oracle making PSPACE IP-friendly, B is a Forrelation encoding making PSPACE readable by BQP while opaque to PH, and C forces P = NP. The advice-robust replacement of B by a random oracle via the proxy quantity rho_t is the technical core. The paper proves its theorems in full with explicit error bounds, concentration arguments, and Borel-Cantelli steps. I spot-checked the proxy approximation, the Forrelation-opacity lemma, the parameter choices in Corollaries 5.3-5.5, and the hybrid argument in Theorem 5.6; they close. The paper is also careful not to overclaim: Remark 4.6 explicitly notes that IP^O = PSPACE^O is not shown for the full oracle.

The soft spots are real but localized. The first half of Theorem 4.12 is disclosed as LLM-originated, and Lemma 4.7 is asserted as "the exact same argument" as Lemma 35 of AIK22 without a proof. That matters because Test^O is an existential search made polynomial-time via P = NP, and the AC^0 flattening of nested C-oracle queries is exactly where an adaptation could fail. The reader's checks of the conditional-independence step and the Hoeffding slack close, but the residual risk is the asserted adaptation itself. This needs a human-written, fully expanded proof before I would call Theorem 1.3(3-5) settled. Appendix B is also LLM-originated; Lemma B.6 is plausible but should be human-verified. The footnote citing [Ope26] is an unpublished preprint and should be replaced or justified. The compressed step in Theorem 5.6 where Corollary 5.5 is applied "individually to each index" deserves one more sentence of detail.

Who this is for: anyone working on PoQ, OSP, quantum cryptography from weak primitives, or oracle separations in quantum complexity. The paper is important enough that the right outcome is peer review, not desk rejection. It should be accepted after the LLM-disclosed passages get human-written proofs and Lemma 4.7 is expanded.

What would settle it

Exhibit a polynomial-size oracle circuit family $\{C_n\}$ such that for a non-negligible fraction of oracles $O$ from the paper's distribution $D$, the circuit $C_n^O$ agrees with salted majority $h_O$ on at least a $1-\delta$ fraction of inputs for infinitely many $n$; that directly refutes Theorem 4.12, the engine of the proof-of-quantumness result. A cheaper check targets the internal replacement step: estimate the proxy $\rho_t$ under $D$ and under $D^{(2n)}$ at any feasible $n$, and if the two differ by more than the $2^{-\Omega(n^2)}$ allowance, the advice-dependent swap of the Forrelated oracle for a random one fails, and with it proof-of-quantumness soundness. On the quantum side, the analogue is a polynomial-bit classical description $c(U)$ that lets a query-bounded distinguisher tell the unitary oracle $U$ from a freshly sampled one with non-negligible advantage, which would refute Corollary 5.4.

Referee report

Significance

If the proofs are completed, the results are significant: they refute the relativized forms of the conjectures that proofs of quantumness imply BPP ≠ NP and that qv-OSP implies BQP ≠ QCMA, and they place barriers on relativizing cryptographic constructions from these primitives. The paper has notable strengths: the oracle constructions are explicit and self-contained, there are no fitted parameters, error bounds are tracked through concentration and Borel-Cantelli arguments, and the authors are candid about the provenance of the most delicate proof step and about the limitations of their relativized statements. The two major comments below concern load-bearing proof passages rather than presentation, and both appear fixable within the scope of the manuscript, so my recommendation is major revision rather than rejection.

Major objections (2)

[Section 4.4, Lemma 4.9 and Eq. (3)] The hybrid argument claims that, after conditioning on M_{i,j}^{O}(x_{i,j}) = 1, 'all portions of the input to C′ besides B_i((M_{i,j},x_{i,j}),·) are independent of B_i((M_{i,j},x_{i,j}),·)', because i = t > sqrt(t). This independence is not justified for the higher-level oracles that Lemma 4.7 feeds into C′. The circuit C′ takes as input B_l for levels l up to t^{2d}-1, and for any l > i^2 the distribution of B_l((M′,x′),·) is determined by whether M′^O(x′) accepts, where M′ is allowed to query O_{⌊sqrt(l)⌋}, which includes B_i. Hence the auxiliary input to C′ can be correlated with the Forrelation/random instance being swapped, and Lemma 3.10, which requires auxiliary distributions independent of the problem input, does not apply as written. This is load-bearing: Eq. (5) and the 2^{-Ω(n^2)} replacement bound feed directly into Theorem 4.12, and Theorem 1.3(3)-(5) all terminate there. The proof should either restrict the B-level range so that no queried B_l can depend on B_i and explain how the hybrid handles all i with T(n) > i^2, or provide a nested argument controlling the correlation.
[Section 5.2, Corollary 5.3] The replacement of RO_n by a fresh random oracle is justified by Corollary 3.25, but that lemma applies to algorithms whose only f-dependent input is a classical advice string c(f) and the q sampled values f(X_i). In Corollary 5.3 the f-dependent information is aux_{RO_n}, a quantum state internal to Simaux; in particular auxMix contains the full columns RO_n(k,·) for the sampled keys k in K* encoded as |RO_n(k,y)⟩ registers. A distinguisher D in the proof of Corollary 3.25 makes only q classical queries to f and cannot prepare this state, so the stated bound (q+n+1)L(n)/2^{n/2} + 2^{-n} is not derived from the lemma as written. The proof's notation also blurs whether aux is an input to A or internal to the simulator. Since Corollaries 5.4 and 5.5, Theorem 5.6, and Claim 5.11 all depend on Corollary 5.3, this issue is load-bearing for Theorem 1.8. The manuscript should either state and prove a quantum-advice version of the presampling bound, or show that aux_{RO_n} is equivalent, for the algorithms under consideration, to q classical samples from RO_n.

Minor objections (4)

[Section 4.4, proof of Lemma 4.9] The proof sets t = i and t′ = T(i)^2, but the machine M in Lemma 4.9 is run on inputs of length s(n), so its runtime bound is T(n), not T(i); the notation should be reconciled, and a comment should state the constant d is chosen uniformly for the polynomial p∘s.
[Section 4.4, Eq. (4)] The final line of the display appears to omit the factor T(n) from the summation when writing '= 1/2^{Ω(n^2)}'; the conclusion is still correct since T(n) is polynomial, but the displayed equality should be written precisely.
[Definition 3.26 and Corollary 4.17] The paper defines qv-PoQ by allowing the verifier to be QPT while retaining the soundness condition against nonuniform PPT classical provers; this is a defensible model, but it should be stated explicitly because Corollary 4.17's two-message protocol is only argued secure against a classical prover, whereas the term 'quantumly-verifiable proof of quantumness' could naturally be misread as security against quantum provers.
[Footnote 2 and Corollary 1.4] The informal claim that BQP = PSPACE rules out nearly all forms of quantum cryptography is justified by a citation to an unpublished OpenAI preprint [Ope26]; for a formal corollary, the dependence on this source should be stated explicitly or replaced by a peer-reviewed statement of the underlying unitary synthesis fact.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

This paper constructs oracle worlds in which proofs of quantumness exist even though P = NP, and quantum-verifier oblivious state preparation exists even though BQP = QCMA.

The reading

The paper asks whether quantum advantage carries hidden complexity-theoretic costs: does the existence of a verifiable quantum-speedup task force some complexity classes to separate? In relativized worlds — worlds with an idealized black box every machine may query — the answer it argues for is no. It constructs a classical oracle under which $P = NP$ and $BQP = PSPACE$, yet a polynomial-round public-coin proof of quantumness exists (an interactive protocol a quantum prover passes and no efficient classical prover can), backed by a language in $IP \subseteq BQP$ that is hard on average against $P/poly$. It constructs a second, unitary oracle under which $BQP = QCMA$, yet a four-message quantum-verifier oblivious state preparation protocol exists (a protocol that remotely creates a quantum state in the prover's lab while keeping its classical description from the prover). If these constructions are sound, the conjectures that proofs of quantumness imply $BPP \neq NP$ and that qv-OSP implies $BQP \neq QCMA$ fail in relativized worlds, and no relativizing proof can build classical or quantum cryptography from such primitives.

What carries the argument

Two mechanisms carry the two results. For the classical oracle, the construction is a three-part oracle $(A, B, C)$: $A$ exposes the multilinear extension over the field $F_{2^d}$ of a random function, making $IP = PSPACE$ hold in relativized, algebrized form; $B$ encodes PSPACE computations under the Forrelation distribution (a distribution a quantum algorithm can distinguish from uniform with few queries while constant-depth circuits cannot), so quantum polynomial time decodes the encoded answers and classical circuits see only randomness; $C$ is a recursively defined NP oracle that forces $P = NP$. The hardness engine is salted majority — whether the output column of a random function at a random salt $x$ has more ones than zeros — proved hard on average against $P/poly$ by first replacing the Forrelated oracle $B$ with a random oracle through a computable proxy $\rho_t$ (the step the authors call the hardest part of the proof), then applying the constant-depth majority lower bound for circuits with parity gates together with a circuit direct-product theorem. For the unitary oracle, the mechanism is a state-preparation oracle $(SG, Expand, Mix)$ built from Haar-random states and a random oracle; it yields a claw-state generator — a protocol where the verifier learns two strings while the prover holds their superposition — and hence qv-OSP, while $BQP = QCMA$ follows from showing that no polynomial-bit classical description of the oracle lets a query-bounded algorithm distinguish it from a fresh one (superconcentration of Haar states plus presampling of the random oracle), lifted from state-preparation channels to unitaries by simulation lemmas for state-preparation unitaries.

Extended reading notes

Core claim

The paper's central claim is that two quantum-advantage primitives are compatible, in relativized worlds, with the collapse of the nondeterministic classes they are widely believed to separate. Theorem 1.3 exhibits a classical oracle $O$ with $P^O = NP^O$ and $BQP^O = PSPACE^O$, together with a language in $IP^O \subseteq BQP^O$ that is hard on average against $P^O/poly$; from that language the authors derive a polynomial-round public-coin proof of quantumness and a two-message quantumly-verifiable proof of quantumness, while also proving that constant-round proofs of quantumness do not exist relative to the same oracle. Theorem 1.8 exhibits a unitary oracle $U$ with $BQP^U = QCMA^U$ relative to which a four-message quantum-verifier oblivious state preparation protocol, built from a claw-state generator, exists. The authors present both results as oracle evidence that the conjectures 'proofs of quantumness imply $BPP \neq NP$' and 'qv-OSP implies $BQP \neq QCMA$' fail relativized, and that no relativizing construction derives classical or quantum cryptography (one-way functions, commitments, efficiently verifiable one-way puzzles, oblivious transfer, and related objects) from these primitives.

Load-bearing premise

The load-bearing premise is the proxy step inside Theorem 4.12: the computable quantity $\rho_t$ must track the advice-dependent success probability tightly enough that the Forrelation-encoded PSPACE oracle $B$ can be replaced by a random oracle even when the advice string may depend on $B$, with the loss kept below $2^{-\Omega(n^2)}$; the authors flag this as the hardest part of the proof, and a larger loss breaks both salted-majority hardness and proof-of-quantumness soundness.

Editorial extensions

If this is right

If the classical result is sound, no relativizing construction builds most classical or quantum cryptographic primitives — in particular anything implying one-way functions or quantum commitments — from polynomial-round proofs of quantumness or two-message quantumly-verifiable proofs of quantumness, and in particular no relativizing construction derives oblivious state preparation or proofs of qua
Relative to the constructed worlds, the conjectures that proofs of quantumness imply $BPP \neq NP$ and that qv-OSP implies $BQP \neq QCMA$ are false relativized; any unrelativized implication would have to use non-relativizing techniques.
Constant-round proofs of quantumness provably do not exist relative to the classical oracle (Corollary 4.16), so there is no relativizing round-reduction from polynomial-round PoQ or two-message qv-PoQ to constant-round PoQ (Corollary 1.5), and no relativizing constant-round construction of classical verification of quantum computation from them (Corollary 1.6).
No relativizing construction takes four-message qv-OSP, quantumly-verifiable proofs of quantum memory, or search-secure QCCC oblivious transfer to efficiently verifiable one-way puzzles, post-quantum one-way functions, or classically implementable oblivious transfer (Corollary 1.9).
Relative to the classical oracle, a language hard on average for $P^O/poly$ — hence outside the polynomial hierarchy relative to the oracle — has an interactive proof with a classical verifier and a quantum-polynomial-time honest prover (Corollary 1.7).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial extension: because the paper's barriers are relativizing, a natural next target is whether the same oracle template separates other 'advantage implies structure' conjectures, for example whether sampling-based quantum advantage over classical distributions can also coexist with $P = NP$ in some relativized world; the paper only treats decision problems and interactive protocols.
Editorial extension: the oracle world admits polynomial-round proofs of quantumness while forbidding constant-round ones (Corollary 4.16), so the minimal round complexity at which a quantum prover beats classical provers relative to that oracle is an open, well-defined quantity; identifying it would show exactly where non-relativizing round-reduction arguments would have to enter.
Editorial extension: the claw-state generator's security is proved against provers with classical advice about the oracle; testing it against provers with quantum advice about the oracle is the natural next adversary model, since quantum advice about Haar-random states behaves very differently from classical advice.

Original abstract

We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-04: 1 request, 7,207 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.59 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.09 · compares with prior results 0.16 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation.	background 0.80	0.26	0.05	unclear 0.88
s1	We show that both of these objects can coexist with the easiness of nondeterministic computation.	result 0.98	0.92	0.72	asserted 0.97
s2	That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$.	result 0.85	0.89	0.65	hedged possibility 0.73
s3	In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist.	result 0.90	0.93	0.23	asserted 1.00
s4	In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$.	result 0.98	0.87	0.07	asserted 1.00
s5	We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists.	result 0.88	0.95	0.14	asserted 1.00
s6	These oracle separations directly imply a number of related consequences.	interpretation 0.93	0.71	0.06	asserted 0.97
s7	For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof.	interpretation 0.99	0.86	0.22	asserted 0.98
s8	Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.	interpretation 0.98	0.87	0.13	asserted 0.99

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (58)

[1]

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Lance Fortnow and Salil P. Vadhan, editors, 43rd Annual ACM Symposium on Theory of Computing , pages 333--342, San Jose, CA, USA, June 6--8, 2011. ACM Press

View on Pith 2011
[2]

Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th Annual ACM Symposium on Theory of Computing , pages 307--316, Portland, OR, USA, June 14--17, 2015. ACM Press

View on Pith 2015
[3]

Scott Aaronson. BQP and the polynomial hierarchy. In Leonard J. Schulman, editor, 42nd Annual ACM Symposium on Theory of Computing , pages 141--150, Cambridge, MA, USA, June 5--8, 2010. ACM Press

View on Pith 2010
[4]

Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing , 2(4):14:1--14:9, 2021

View on Pith 2021
[5]

Bar s Ayd nl o g lu and Eric Bach. Affine relativization: Unifying the algebrization and relativization barriers. Electronic Colloquium on Computational Complexity, Report TR16-040, Revision 3, 2017

View on Pith 2017
[6]

Prabhanjan Ananth and Eli Goldin. Less is more: On copy complexity in quantum cryptography. Cryptology ePrint Archive, Report 2025/1855, 2025

View on Pith 2025
[7]

Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd Annual ACM Symposium on Theory of Computing , pages 255--268, Chicago, IL, USA, June 22--26, 2020. ACM Press

View on Pith 2020
[8]

Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin. Cryptography in the common Haar state model: Feasibility results and separations. In Elette Boyle and Mohammad Mahmoody, editors, TCC 2024: 22nd Theory of Cryptography Conference, Part II , volume 15365 of Lecture Notes in Computer Science , pages 94--125, Milan, Italy, December 2--6, 2024. Springer, Cha...

View on Pith 2024
[9]

Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of bqp. In Proceedings of the 37th Computational Complexity Conference , CCC '22, Dagstuhl, DEU, 2022. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

View on Pith 2022
[10]

Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing , pages 731--740, Victoria, BC, Canada, May 17--20, 2008. ACM Press

View on Pith 2008
[11]

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing , 26(5):1510--1523, 1997

View on Pith 1997
[12]

Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science , pages 320--331, Paris, France, October 7--9, 2018. IEEE Computer Society Press

View on Pith 2018
[13]

Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, and Avishay Tal. BQP IP does not relativize, 2026

View on Pith 2026
[14]

Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 467(2126):459--472, 2011. arXiv:1005.1407

View on Pith Pith review arXiv 2011
[15]

James Bartusek and Dakshita Khurana. On the power of oblivious state preparation. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology -- CRYPTO 2025, Part II , volume 16001 of Lecture Notes in Computer Science , pages 575--607, Santa Barbara, CA, USA, August 17--21, 2025. Springer, Cham, Switzerland

View on Pith 2025
[16]

Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. A new world in the depths of microcrypt: Separating OWSGs and quantum money from QEFID . In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology -- EUROCRYPT 2025, Part VII , volume 15607 of Lecture Notes in Computer Science , pages 23--52, Madrid, Spain, May...

View on Pith 2025
[17]

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In 35th Annual ACM Symposium on Theory of Computing , pages 59--68, San Diego, CA, USA, June 9--11, 2003. ACM Press

View on Pith 2003
[18]

Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan H stad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences , 49(1):24--39, 1994

View on Pith 1994
[19]

Boyang Chen, Andrea Coladangelo, and Or Sattath. The power of a single haar random state: Constructing and separating quantum pseudorandomness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology -- EUROCRYPT 2025, Part VII , volume 15607 of Lecture Notes in Computer Science , pages 108--137, Madrid, Spain, May 4--8, 2025. Springer, Cha...

View on Pith 2025
[20]

Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger. Random oracles and non-uniformity. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology -- EUROCRYPT 2018, Part I , volume 10820 of Lecture Notes in Computer Science , pages 227--258, Tel Aviv, Israel, April 29 -- May 3, 2018. Springer, Cham, Switzerland

View on Pith 2018
[21]

Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology -- CRYPTO 2024, Part VII , volume 14926 of Lecture Notes in Computer Science , pages 215--248, Santa Barbara, CA, USA, August 18--22, 2024. Springer, Cham, Switzerland

View on Pith 2024
[22]

Alper C akan, Vipul Goyal, and Justin Raizes. How to delete without a trace: Certified deniability in a quantum world. In Advances in Cryptology – CRYPTO 2026: 46th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–20, 2026, Proceedings, Part V , page 183–214, Berlin, Heidelberg, 2026. Springer-Verlag

View on Pith 2026
[23]

Boyang Chen, Yiming Wang, and Ziyi Xie. The breakdown of classical minicrypt equivalences in the quantum-computation classical-communication model, 2026

View on Pith 2026
[24]

Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, and John Wright. Quantum lazy sampling and path recording for any group, 2026

View on Pith 2026
[25]

Lance Fortnow. A simple proof of Toda 's theorem. Theory of Computing , 5:135--140, 2009

View on Pith 2009
[26]

Lance Fortnow and Michael Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters , 28(5):249--251, 1988

View on Pith 1988
[27]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing , pages 113--122, Victoria, BC, Canada, May 17--20, 2008. ACM Press

View on Pith 2008
[28]

Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. CountCrypt : Quantum cryptography between QCMA and PP . Cryptology ePrint Archive, Report 2024/1707, 2024

View on Pith 2024
[29]

Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In 18th Annual ACM Symposium on Theory of Computing , pages 59--68, Berkeley, CA, USA, May 28--30, 1986. ACM Press

View on Pith 1986
[30]

Dmitry Grinko and Satoshi Yoshida. Quantum simulation of random unitaries from clebsch-gordan transforms, 2026

View on Pith 2026
[31]

Eli Goldin and Mark Zhandry. Translating between the common haar random state model and the unitary model. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology -- CRYPTO 2025, Part II , volume 16001 of Lecture Notes in Computer Science , pages 269--300, Santa Barbara, CA, USA, August 17--21, 2025. Springer, Cham, Switzerland

View on Pith 2025
[32]

Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In 64th Annual Symposium on Foundations of Computer Science , pages 363--390, Santa Cruz, CA, USA, November 6--9, 2023. IEEE Computer Society Press

View on Pith 2023
[33]

Minki Hhan, Tomoyuki Morimae, Yasuaki Okinaka, and Takashi Yamakawa. Proofs of quantum memory. Cryptology ePrint Archive, Report 2025/1837, 2025

View on Pith 2025
[34]

William M. Hoza. A technique for hardness amplification against ac0. computational complexity , 35(2):12, Sep 2026

View on Pith 2026
[35]

Minki Hhan and Shogo Yamada. Pseudorandom function-like states from common haar unitary. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025: 23rd Theory of Cryptography Conference, Part III , volume 16270 of Lecture Notes in Computer Science , pages 134--165, Aarhus, Denmark, December 1--5, 2025. Springer, Cham, Switzerland

View on Pith 2025
[36]

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson. Uniform direct product theorems: Simplified, optimized, and derandomized. SIAM Journal on Computing , 39(4):1637--1665, 2010

View on Pith 2010
[37]

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Barna Saha and Rocco A. Servedio, editors, 55th Annual ACM Symposium on Theory of Computing , pages 1617--1628, Orlando, FL, USA, June 20--23, 2023. ACM Press

View on Pith 2023
[38]

Swastik Kopparty, Jason Perry, and Brian Garnett. Lecture 4: AC0 lower bounds and pseudorandomness. 2013

View on Pith 2013
[39]

William Kretschmer. Quantum Pseudorandomness and Classical Complexity . Leibniz Int. Proc. Inf. , 197:2:1--2:20, 2021

View on Pith 2021
[40]

Urmila Mahadev. Classical verification of quantum computations. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science , pages 259--267, Paris, France, October 7--9, 2018. IEEE Computer Society Press

View on Pith 2018
[41]

Atul Mantri. Classical verification of quantum computation beyond the polynomial hierarchy, 2026

View on Pith 2026
[42]

Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups . Cambridge Tracts in Mathematics. Cambridge University Press, 2019

View on Pith 2019
[43]

Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In Michal Kouck\' y and Nikhil Bansal, editors, 57th Annual ACM Symposium on Theory of Computing , pages 806--809, Prague, Czechia, June 23--27, 2025. ACM Press

View on Pith 2025
[44]

Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. Cryptographic characterization of quantum advantage. In Michal Kouck\' y and Nikhil Bansal, editors, 57th Annual ACM Symposium on Theory of Computing , pages 1863--1874, Prague, Czechia, June 23--27, 2025. ACM Press

View on Pith 2025
[45]

Tomoyuki Morimae and Takashi Yamakawa. Proofs of quantumness from trapdoor permutations. In Yael Tauman Kalai, editor, ITCS 2023: 14th Innovations in Theoretical Computer Science Conference , volume 251, pages 87:1--87:14, Cambridge, MA, USA, January 10--13, 2023. Leibniz International Proceedings in Informatics (LIPIcs)

View on Pith 2023
[46]

Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science , pages 369--377, New York, NY, USA, October 17--19, 1999. IEEE Computer Society Press

View on Pith 1999
[47]

OpenAI . Polynomial-Time Unitary Synthesis from a Boolean Oracle . OpenAI Math Release preprint, October 2026

View on Pith 2026
[48]

A. A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR , 41(4):333--338, April 1987

View on Pith 1987
[49]

Ran Raz and Avishay Tal. Oracle separation of BQP and PH . In Moses Charikar and Edith Cohen, editors, 51st Annual ACM Symposium on Theory of Computing , pages 13--23, Phoenix, AZ, USA, June 23--26, 2019. ACM Press

View on Pith 2019
[50]

Adi Shamir. IP = PSPACE . In 31st Annual Symposium on Foundations of Computer Science , pages 11--15, St. Louis, MO, USA, October 22--24, 1990. IEEE Computer Society Press

View on Pith 1990
[51]

Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science , pages 124--134, Santa Fe, NM, USA, November 20--22, 1994. IEEE Computer Society Press

View on Pith 1994
[52]

Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing , 26(5):1474--1483, 1997

View on Pith 1997
[53]

Larry J. Stockmeyer. The complexity of approximate counting (preliminary version). In 15th Annual ACM Symposium on Theory of Computing , pages 118--126, Boston, MA, USA, April 25--27, 1983. ACM Press

View on Pith 1983
[54]

Omri Shmueli and Mark Zhandry. On one-shot signatures, quantum vs. classical binding, and obfuscating permutations. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology -- CRYPTO 2025, Part II , volume 16001 of Lecture Notes in Computer Science , pages 350--383, Santa Barbara, CA, USA, August 17--21, 2025. Springer, Cham, Switzerland

View on Pith 2025
[55]

Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help, 2026

View on Pith 2026
[56]

Kabir Tomer and Mark Zhandry. On the cryptographic foundations of interactive quantum advantage. In STOC 2026 , 2026. arXiv:2510.05082

View on Pith arXiv 2026
[57]

Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. In 63rd Annual Symposium on Foundations of Computer Science , pages 69--74, Denver, CO, USA, October 31 -- November 3, 2022. IEEE Computer Society Press

View on Pith 2022
[58]

Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology -- CRYPTO 2019, Part II , volume 11693 of Lecture Notes in Computer Science , pages 239--268, Santa Barbara, CA, USA, August 18--22, 2019. Springer, Cham, Switzerland

View on Pith 2019

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Lance Fortnow and Salil P. Vadhan, editors, 43rd Annual ACM Symposium on Theory of Computing , pages 333--342, San Jose, CA, USA, June 6--8, 2011. ACM Press

View on Pith 2011

[2] [2]

Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th Annual ACM Symposium on Theory of Computing , pages 307--316, Portland, OR, USA, June 14--17, 2015. ACM Press

View on Pith 2015

[3] [3]

Scott Aaronson. BQP and the polynomial hierarchy. In Leonard J. Schulman, editor, 42nd Annual ACM Symposium on Theory of Computing , pages 141--150, Cambridge, MA, USA, June 5--8, 2010. ACM Press

View on Pith 2010

[4] [4]

Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing , 2(4):14:1--14:9, 2021

View on Pith 2021

[5] [5]

Bar s Ayd nl o g lu and Eric Bach. Affine relativization: Unifying the algebrization and relativization barriers. Electronic Colloquium on Computational Complexity, Report TR16-040, Revision 3, 2017

View on Pith 2017

[6] [6]

Prabhanjan Ananth and Eli Goldin. Less is more: On copy complexity in quantum cryptography. Cryptology ePrint Archive, Report 2025/1855, 2025

View on Pith 2025

[7] [7]

Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd Annual ACM Symposium on Theory of Computing , pages 255--268, Chicago, IL, USA, June 22--26, 2020. ACM Press

View on Pith 2020

[8] [8]

Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin. Cryptography in the common Haar state model: Feasibility results and separations. In Elette Boyle and Mohammad Mahmoody, editors, TCC 2024: 22nd Theory of Cryptography Conference, Part II , volume 15365 of Lecture Notes in Computer Science , pages 94--125, Milan, Italy, December 2--6, 2024. Springer, Cha...

View on Pith 2024

[9] [9]

Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of bqp. In Proceedings of the 37th Computational Complexity Conference , CCC '22, Dagstuhl, DEU, 2022. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

View on Pith 2022

[10] [10]

Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing , pages 731--740, Victoria, BC, Canada, May 17--20, 2008. ACM Press

View on Pith 2008

[11] [11]

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing , 26(5):1510--1523, 1997

View on Pith 1997

[12] [12]

Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science , pages 320--331, Paris, France, October 7--9, 2018. IEEE Computer Society Press

View on Pith 2018

[13] [13]

Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, and Avishay Tal. BQP IP does not relativize, 2026

View on Pith 2026

[14] [14]

Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 467(2126):459--472, 2011. arXiv:1005.1407

View on Pith Pith review arXiv 2011

[15] [15]

James Bartusek and Dakshita Khurana. On the power of oblivious state preparation. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology -- CRYPTO 2025, Part II , volume 16001 of Lecture Notes in Computer Science , pages 575--607, Santa Barbara, CA, USA, August 17--21, 2025. Springer, Cham, Switzerland

View on Pith 2025

[16] [16]

Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. A new world in the depths of microcrypt: Separating OWSGs and quantum money from QEFID . In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology -- EUROCRYPT 2025, Part VII , volume 15607 of Lecture Notes in Computer Science , pages 23--52, Madrid, Spain, May...

View on Pith 2025

[17] [17]

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In 35th Annual ACM Symposium on Theory of Computing , pages 59--68, San Diego, CA, USA, June 9--11, 2003. ACM Press

View on Pith 2003

[18] [18]

Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan H stad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences , 49(1):24--39, 1994

View on Pith 1994

[19] [19]

Boyang Chen, Andrea Coladangelo, and Or Sattath. The power of a single haar random state: Constructing and separating quantum pseudorandomness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology -- EUROCRYPT 2025, Part VII , volume 15607 of Lecture Notes in Computer Science , pages 108--137, Madrid, Spain, May 4--8, 2025. Springer, Cha...

View on Pith 2025

[20] [20]

Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger. Random oracles and non-uniformity. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology -- EUROCRYPT 2018, Part I , volume 10820 of Lecture Notes in Computer Science , pages 227--258, Tel Aviv, Israel, April 29 -- May 3, 2018. Springer, Cham, Switzerland

View on Pith 2018

[21] [21]

Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology -- CRYPTO 2024, Part VII , volume 14926 of Lecture Notes in Computer Science , pages 215--248, Santa Barbara, CA, USA, August 18--22, 2024. Springer, Cham, Switzerland

View on Pith 2024

[22] [22]

Alper C akan, Vipul Goyal, and Justin Raizes. How to delete without a trace: Certified deniability in a quantum world. In Advances in Cryptology – CRYPTO 2026: 46th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–20, 2026, Proceedings, Part V , page 183–214, Berlin, Heidelberg, 2026. Springer-Verlag

View on Pith 2026

[23] [23]

Boyang Chen, Yiming Wang, and Ziyi Xie. The breakdown of classical minicrypt equivalences in the quantum-computation classical-communication model, 2026

View on Pith 2026

[24] [24]

Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, and John Wright. Quantum lazy sampling and path recording for any group, 2026

View on Pith 2026

[25] [25]

Lance Fortnow. A simple proof of Toda 's theorem. Theory of Computing , 5:135--140, 2009

View on Pith 2009

[26] [26]

Lance Fortnow and Michael Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters , 28(5):249--251, 1988

View on Pith 1988

[27] [27]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing , pages 113--122, Victoria, BC, Canada, May 17--20, 2008. ACM Press

View on Pith 2008

[28] [28]

Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. CountCrypt : Quantum cryptography between QCMA and PP . Cryptology ePrint Archive, Report 2024/1707, 2024

View on Pith 2024

[29] [29]

Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In 18th Annual ACM Symposium on Theory of Computing , pages 59--68, Berkeley, CA, USA, May 28--30, 1986. ACM Press

View on Pith 1986

[30] [30]

Dmitry Grinko and Satoshi Yoshida. Quantum simulation of random unitaries from clebsch-gordan transforms, 2026

View on Pith 2026

[31] [31]

Eli Goldin and Mark Zhandry. Translating between the common haar random state model and the unitary model. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology -- CRYPTO 2025, Part II , volume 16001 of Lecture Notes in Computer Science , pages 269--300, Santa Barbara, CA, USA, August 17--21, 2025. Springer, Cham, Switzerland

View on Pith 2025

[32] [32]

Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In 64th Annual Symposium on Foundations of Computer Science , pages 363--390, Santa Cruz, CA, USA, November 6--9, 2023. IEEE Computer Society Press

View on Pith 2023

[33] [33]

Minki Hhan, Tomoyuki Morimae, Yasuaki Okinaka, and Takashi Yamakawa. Proofs of quantum memory. Cryptology ePrint Archive, Report 2025/1837, 2025

View on Pith 2025

[34] [34]

William M. Hoza. A technique for hardness amplification against ac0. computational complexity , 35(2):12, Sep 2026

View on Pith 2026

[35] [35]

Minki Hhan and Shogo Yamada. Pseudorandom function-like states from common haar unitary. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025: 23rd Theory of Cryptography Conference, Part III , volume 16270 of Lecture Notes in Computer Science , pages 134--165, Aarhus, Denmark, December 1--5, 2025. Springer, Cham, Switzerland

View on Pith 2025

[36] [36]

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson. Uniform direct product theorems: Simplified, optimized, and derandomized. SIAM Journal on Computing , 39(4):1637--1665, 2010

View on Pith 2010

[37] [37]

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Barna Saha and Rocco A. Servedio, editors, 55th Annual ACM Symposium on Theory of Computing , pages 1617--1628, Orlando, FL, USA, June 20--23, 2023. ACM Press

View on Pith 2023

[38] [38]

Swastik Kopparty, Jason Perry, and Brian Garnett. Lecture 4: AC0 lower bounds and pseudorandomness. 2013

View on Pith 2013

[39] [39]

William Kretschmer. Quantum Pseudorandomness and Classical Complexity . Leibniz Int. Proc. Inf. , 197:2:1--2:20, 2021

View on Pith 2021

[40] [40]

Urmila Mahadev. Classical verification of quantum computations. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science , pages 259--267, Paris, France, October 7--9, 2018. IEEE Computer Society Press

View on Pith 2018

[41] [41]

Atul Mantri. Classical verification of quantum computation beyond the polynomial hierarchy, 2026

View on Pith 2026

[42] [42]

Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups . Cambridge Tracts in Mathematics. Cambridge University Press, 2019

View on Pith 2019

[43] [43]

Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In Michal Kouck\' y and Nikhil Bansal, editors, 57th Annual ACM Symposium on Theory of Computing , pages 806--809, Prague, Czechia, June 23--27, 2025. ACM Press

View on Pith 2025

[44] [44]

Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. Cryptographic characterization of quantum advantage. In Michal Kouck\' y and Nikhil Bansal, editors, 57th Annual ACM Symposium on Theory of Computing , pages 1863--1874, Prague, Czechia, June 23--27, 2025. ACM Press

View on Pith 2025

[45] [45]

Tomoyuki Morimae and Takashi Yamakawa. Proofs of quantumness from trapdoor permutations. In Yael Tauman Kalai, editor, ITCS 2023: 14th Innovations in Theoretical Computer Science Conference , volume 251, pages 87:1--87:14, Cambridge, MA, USA, January 10--13, 2023. Leibniz International Proceedings in Informatics (LIPIcs)

View on Pith 2023

[46] [46]

Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science , pages 369--377, New York, NY, USA, October 17--19, 1999. IEEE Computer Society Press

View on Pith 1999

[47] [47]

OpenAI . Polynomial-Time Unitary Synthesis from a Boolean Oracle . OpenAI Math Release preprint, October 2026

View on Pith 2026

[48] [48]

A. A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR , 41(4):333--338, April 1987

View on Pith 1987

[49] [49]

Ran Raz and Avishay Tal. Oracle separation of BQP and PH . In Moses Charikar and Edith Cohen, editors, 51st Annual ACM Symposium on Theory of Computing , pages 13--23, Phoenix, AZ, USA, June 23--26, 2019. ACM Press

View on Pith 2019

[50] [50]

Adi Shamir. IP = PSPACE . In 31st Annual Symposium on Foundations of Computer Science , pages 11--15, St. Louis, MO, USA, October 22--24, 1990. IEEE Computer Society Press

View on Pith 1990

[51] [51]

Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science , pages 124--134, Santa Fe, NM, USA, November 20--22, 1994. IEEE Computer Society Press

View on Pith 1994

[52] [52]

Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing , 26(5):1474--1483, 1997

View on Pith 1997

[53] [53]

Larry J. Stockmeyer. The complexity of approximate counting (preliminary version). In 15th Annual ACM Symposium on Theory of Computing , pages 118--126, Boston, MA, USA, April 25--27, 1983. ACM Press

View on Pith 1983

[54] [54]

Omri Shmueli and Mark Zhandry. On one-shot signatures, quantum vs. classical binding, and obfuscating permutations. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology -- CRYPTO 2025, Part II , volume 16001 of Lecture Notes in Computer Science , pages 350--383, Santa Barbara, CA, USA, August 17--21, 2025. Springer, Cham, Switzerland

View on Pith 2025

[55] [55]

Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help, 2026

View on Pith 2026

[56] [56]

Kabir Tomer and Mark Zhandry. On the cryptographic foundations of interactive quantum advantage. In STOC 2026 , 2026. arXiv:2510.05082

View on Pith arXiv 2026

[57] [57]

Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. In 63rd Annual Symposium on Foundations of Computer Science , pages 69--74, Denver, CO, USA, October 31 -- November 3, 2022. IEEE Computer Society Press

View on Pith 2022

[58] [58]

Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology -- CRYPTO 2019, Part II , volume 11693 of Lecture Notes in Computer Science , pages 239--268, Santa Barbara, CA, USA, August 18--22, 2019. Springer, Cham, Switzerland

View on Pith 2019