pith. machine review for the scientific record. sign in

arxiv: 2604.27886 · v1 · submitted 2026-04-30 · 🪐 quant-ph · cs.CC

Recognition: unknown

Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

Yupan Liu , Pei Wu
Authors on Pith no claims yet

Pith reviewed 2026-05-07 05:58 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords StoqMA(2)unentanglementstoquasticMerlin-Arthurproof systemsquantum complexitySum-of-Squaresdistribution testing
0
0 comments X

The pith

StoqMA(2) contains NP with Õ(√n)-qubit unentangled stoquastic proofs and is contained in EXP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper studies StoqMA(2), the class of languages verifiable by Merlin-Arthur protocols with two unentangled stoquastic quantum proofs. It shows that NP is contained in StoqMA(2) using proofs of size roughly the square root of the input length in qubits and with a very small completeness error of 2 to the minus polylog n. At the same time, it shows that StoqMA(2) is contained in EXP by refining the Sum-of-Squares algorithm, and this containment is optimal under the exponential time hypothesis. The results are obtained by converting existing short-proof QMA(2) protocols into stoquastic versions using distribution testing, and by introducing a rectangular closure testing framework for the upper bounds on variants with better completeness.

Core claim

NP is contained in StoqMA(2) with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}. Conversely, StoqMA(2) is contained in EXP, and with the lower bound this shows the optimality of the Sum-of-Squares algorithm for this class under ETH. StoqMA(2) with one proof is in PSPACE with exponentially small error, and PreciseStoqMA(2) cannot have perfect completeness unless EXP = NEXP. When the completeness error is negligible, StoqMA(k) equals StoqMA(2) for any k greater than or equal to 2.

What carries the argument

Stoquastization of short-proof QMA(2) protocols using distribution testing techniques to create stoquastic versions without destructive interference, together with a new rectangular closure testing framework for proving upper bounds in the nearly perfect completeness regime.

If this is right

  • The Sum-of-Squares algorithm is optimal for deciding StoqMA(2) languages under ETH.
  • StoqMA(2) with one proof is contained in PSPACE even with completeness error 2^{-2^{poly(n)}}.
  • PreciseStoqMA(2) cannot achieve perfect completeness unless EXP equals NEXP.
  • When completeness error is negligible, StoqMA(k) equals StoqMA(2) for k greater than or equal to 2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation between StoqMA(2) and QMA(2) indicates that avoiding destructive interference limits the power that unentanglement can provide in quantum proof systems.
  • Stoquastization techniques may apply to other quantum proof classes to produce semi-classical variants with improved upper bounds.
  • The results could guide the design of verification protocols for sign-problem-free quantum systems by showing how unentanglement adds power without full quantum interference.

Load-bearing premise

Stoquastizing the QMA(2) protocols via distribution testing succeeds without introducing destructive interference or other obstructions that would prevent the resulting protocols from being valid StoqMA(2) proofs.

What would settle it

A subexponential-time algorithm for 3-SAT that succeeds on all instances admitting Õ(√n)-qubit StoqMA(2) proofs would falsify the ETH optimality of the EXP upper bound.

Figures

Figures reproduced from arXiv: 2604.27886 by Pei Wu, Yupan Liu.

Figure 1
Figure 1. Figure 1: Relationships among StoqMA(2), its variants, and other complexity classes. The lower-bound side. We begin by stating our first main lower-bound result for StoqMA(2) with short proofs, as provided in Theorem 1.1. For convenience, we write StoqMA(k) ℓ Jk, c, ∆K for the class of StoqMA(k) proof systems in which each proof has length ℓ(n), completeness c(n), and promise gap ∆(n) := c(n) − s(n), where s(n) deno… view at source ↗
Figure 2
Figure 2. Figure 2: Weak conjunction of stoquastic verifiers view at source ↗
Figure 3
Figure 3. Figure 3: Conjunction of stoquastic verifiers V (1) x1 , V (2) x2 , and V (3) x3 . Theorem 3.16 (ProdStoqMA(k) is closed under direct product, restated). Let  I (j) view at source ↗
read the original abstract

Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\sf StoqMA$, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\sf MA$ and $\sf AM$. Unentanglement similarly gives rise to ${\sf QMA}(2)$, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\sf QMA$ to two unentangled proofs and still has only the trivial $\sf NEXP$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via ${\sf StoqMA}(2)$, the class of unentangled stoquastic Merlin-Arthur proof systems. Although $\sf StoqMA$ is semi-quantum and may collapse to $\sf MA$, ${\sf StoqMA}(2)$ turns out to be surprisingly powerful. We establish the following results: - ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-{\rm polylog}(n)}$. Conversely, ${\sf StoqMA}(2) \subseteq {\sf EXP}$ via the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014); with our lower bound, our refined analysis yields the optimality of this algorithm under ETH. - ${\sf StoqMA}(2)_1 \subseteq {\sf PSPACE}$, and the containment holds with completeness error $2^{-2^{{\rm poly}(n)}}$. - ${\sf PreciseStoqMA}(2)$, a variant of ${\sf StoqMA}(2)$ with exponentially small promise gap, cannot achieve perfect completeness unless ${\sf EXP}={\sf NEXP}$. In contrast, ${\sf PreciseStoqMA}$ achieves perfect completeness, since ${\sf PSPACE} \subseteq {\sf PreciseStoqMA}_1$. - When the completeness error is negligible, ${\sf StoqMA}(k) = {\sf StoqMA}(2)$ for $k\geq 2$. Our lower bounds are obtained by stoquastizing the short-proof ${\sf QMA}(2)$ protocols via distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our new rectangular closure testing framework.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces the complexity class StoqMA(2), consisting of languages decidable by a stoquastic Merlin-Arthur verifier with two unentangled quantum proofs. It establishes that NP is contained in StoqMA(2) using Õ(√n)-qubit proofs with completeness error 2^{-polylog(n)}, and that StoqMA(2) is contained in EXP. This containment is shown to be optimal under the Exponential Time Hypothesis (ETH) via a refined analysis of the Sum-of-Squares algorithm. Additional results include StoqMA(2) with one-sided error being in PSPACE with exponentially small completeness error, that PreciseStoqMA(2) cannot have perfect completeness unless EXP = NEXP, and that StoqMA(k) collapses to StoqMA(2) for k ≥ 2 when the completeness error is negligible. The lower bounds are derived by stoquastizing short-proof QMA(2) protocols using distribution testing, while upper bounds use a new rectangular closure testing framework.

Significance. If the central technical claims hold, particularly the stoquastization without introducing destructive interference or violating unentanglement, this work would be significant for quantum complexity theory. It demonstrates that unentanglement can provide substantial power even in the stoquastic setting, which avoids destructive interference. The optimality result under ETH strengthens the understanding of the Sum-of-Squares algorithm's limitations. The new techniques, such as rectangular closure testing, may find applications in other areas of proof complexity and quantum information. The results position StoqMA(2) as an interesting intermediate class between MA and more powerful quantum classes.

major comments (2)
  1. [Proof of the main containment (Theorem 1)] The stoquastization of short-proof QMA(2) protocols via distribution testing is the load-bearing step for the main containment NP ⊆ StoqMA(2). It is unclear whether the distribution testing procedure preserves the stoquasticity (non-negative off-diagonal entries in the computational basis for the acceptance operator) and the unentangled product-state property of the proofs simultaneously, especially while achieving the claimed completeness error of 2^{-polylog(n)}. A detailed verification that no negative matrix elements are introduced or canceled by phases, and that no entangled measurement is required for certification, is necessary.
  2. [Section on upper bounds and ETH optimality] The refined analysis claiming optimality of the Sum-of-Squares algorithm under ETH for StoqMA(2) ⊆ EXP should include an explicit reduction showing how the Õ(√n) proof size and the specific completeness error lead to the ETH-based time lower bound. The current description relies on external results without detailing the parameter translation.
minor comments (2)
  1. [Introduction] The definition of StoqMA(2)_1 should be provided explicitly upon first use, as it is not standard notation.
  2. [Abstract] The phrase 'our refined analysis yields the optimality' could be clarified by stating which parameters are refined compared to prior work.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, constructive feedback, and recognition of the potential significance of StoqMA(2). We address each major comment below and will incorporate clarifications and additional details into the revised manuscript.

read point-by-point responses

  1. Referee: [Proof of the main containment (Theorem 1)] The stoquastization of short-proof QMA(2) protocols via distribution testing is the load-bearing step for the main containment NP ⊆ StoqMA(2). It is unclear whether the distribution testing procedure preserves the stoquasticity (non-negative off-diagonal entries in the computational basis for the acceptance operator) and the unentangled product-state property of the proofs simultaneously, especially while achieving the claimed completeness error of 2^{-polylog(n)}. A detailed verification that no negative matrix elements are introduced or canceled by phases, and that no entangled measurement is required for certification, is necessary.

    Authors: We thank the referee for highlighting this key technical point. The stoquastization is performed by replacing the original QMA(2) verifier with a distribution-testing procedure that estimates acceptance probabilities via computational-basis measurements on each unentangled proof separately. Because these measurements yield non-negative probabilities and the original short-proof QMA(2) protocols for NP can be realized with stoquastic acceptance operators, the resulting operator has exclusively non-negative off-diagonal entries; no phases are present that could produce cancellations. Unentanglement is preserved because the verifier never performs a joint entangled measurement; each proof is certified via its own marginal distribution. The 2^{-polylog(n)} completeness error is obtained by repeating the test O(polylog(n)) times. In the revision we will add a dedicated subsection containing the explicit matrix-element calculations that verify stoquasticity is maintained and that certification uses only product-state measurements. revision: yes

  2. Referee: [Section on upper bounds and ETH optimality] The refined analysis claiming optimality of the Sum-of-Squares algorithm under ETH for StoqMA(2) ⊆ EXP should include an explicit reduction showing how the Õ(√n) proof size and the specific completeness error lead to the ETH-based time lower bound. The current description relies on external results without detailing the parameter translation.

    Authors: We agree that an explicit parameter translation will strengthen the presentation. The ETH lower bound follows because our StoqMA(2) construction embeds the Õ(√n)-qubit, 2^{-polylog(n)}-error short-proof QMA(2) protocols for 3SAT; the Sum-of-Squares algorithm of Barak et al. then solves the resulting StoqMA(2) instance in 2^{O(√n polylog n)} time. A faster algorithm would therefore solve 3SAT in subexponential time, contradicting ETH. In the revised manuscript we will insert a new subsection that explicitly traces the proof-size and error parameters from the QMA(2) protocols through the stoquastization step to the final ETH-based time lower bound, including the necessary polylog-factor accounting. revision: yes

Circularity Check

0 steps flagged

No circularity: derivations rely on external citations and new constructive frameworks

full rationale

The central containment NP ⊆ StoqMA(2) is obtained by applying distribution testing to convert existing short-proof QMA(2) protocols (from Kobayashi et al.) into stoquastic unentangled verifiers, a constructive reduction whose correctness is argued via sign-pattern preservation and product-state maintenance rather than any self-referential definition or fitted parameter. The EXP upper bound invokes the external Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) without modification that would make the containment tautological. The PSPACE containment for StoqMA(2)_1 and the rectangular closure testing framework are introduced as original tools in the paper. The ETH-optimality corollary combines the new lower bound with the external SOS analysis and does not reduce any claimed result to its own inputs by construction. No equations, self-citations, or ansatzes in the abstract or described chain match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard complexity-theoretic assumptions and techniques. The ETH is invoked for the optimality claim. No free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to conclude optimality of the Sum-of-Squares algorithm for StoqMA(2).

pith-pipeline@v0.9.0 · 5757 in / 1376 out tokens · 48959 ms · 2026-05-07T05:58:59.685499+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Complexity of Stoquastic Sparse Hamiltonians

    cs.CC 2026-05 unverdicted novelty 7.0

    Stoquastic Sparse Hamiltonians is StoqMA-complete and its separable version is StoqMA(2)-complete.

Reference graph

Works this paper leans on

100 extracted references · 97 canonical work pages · cited by 1 Pith paper · 4 internal anchors

  1. [1]

    The power of unentanglement

    Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. The power of unentanglement. Theory of Computing . 5(1):1--42. 2009. https://doi.org/10.4086/toc.2009.v005a001 doi:10.4086/toc.2009.v005a001 . https://arxiv.org/abs/0804.0802 arXiv:0804.0802 . Appearances:\!

    work page doi:10.4086/toc.2009.v005a001 2009

  2. [2]

    Stoquastic PCP vs

    Dorit Aharonov and Alex Bredariol Grilo. Stoquastic PCP vs. randomness. In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019) . pages 1000--1023. IEEE. 2019. https://doi.org/10.1109/FOCS.2019.00065 doi:10.1109/FOCS.2019.00065 . https://arxiv.org/abs/1901.05270 arXiv:1901.05270 . Appearances:\!

    work page doi:10.1109/focs.2019.00065 2019

  3. [3]

    Dorit Aharonov and Alex B. Grilo. Two combinatorial MA -complete problems. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference ( ITCS 2021) . volume 185 of LIPIcs . pages 36:1--36:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2021. https://doi.org/10.4230/LIPIcs.ITCS.2021.36 doi:10.4230/LIPIcs.ITCS.2021.36 . htt...

    work page doi:10.4230/lipics.itcs.2021.36 2021

  4. [4]

    StoqMA vs. MA: the power of error reduction

    Dorit Aharonov, Alex B. Grilo, and Yupan Liu. StoqMA vs. MA : the power of error reduction. Quantum . 9:1853. 2025. https://doi.org/10.22331/Q-2025-09-11-1853 doi:10.22331/Q-2025-09-11-1853 . https://arxiv.org/abs/2010.02835 arXiv:2010.02835 . Appearances:\!

    work page doi:10.22331/q-2025-09-11-1853 2025

  5. [5]

    Adiabatic quantum computation

    Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics . 90(1):015002. 2018. https://doi.org/10.1103/RevModPhys.90.015002 doi:10.1103/RevModPhys.90.015002 . https://arxiv.org/abs/1611.04471 arXiv:1611.04471 . Appearances:\!

    work page doi:10.1103/revmodphys.90.015002 2018

  6. [6]

    Trading group theory for randomness

    L \'a szl \'o Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing . pages 421--429. 1985. https://doi.org/10.1145/22145.22192 doi:10.1145/22145.22192 . Appearances:\!

    work page doi:10.1145/22145.22192 1985

  7. [7]

    Boaz Barak, Fernando G. S. L. Brand \ a o, Aram W. Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012) . pages 307--326. ACM . 2012. https://doi.org/10.1145/2213977.2214006 doi:10.1145/2213977.2214006 . h...

    work page doi:10.1145/2213977.2214006 2012

  8. [8]

    Merlin--Arthur games and stoquastic complexity

    Sergey Bravyi, Arvid J Bessen, and Barbara M Terhal. Merlin--Arthur games and stoquastic complexity. arXiv preprint . 2006. https://arxiv.org/abs/quant-ph/0611021 arXiv:quant-ph/0611021 . Appearances:\!

    work page arXiv 2006

  9. [9]

    Quantum fingerprinting.Phys

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald Wolf d e Wolf. Quantum fingerprinting. Physical Review Letters . 87(16):167902. 2001. https://doi.org/10.1103/PhysRevLett.87.167902 doi:10.1103/PhysRevLett.87.167902 . https://arxiv.org/abs/quant-ph/0102001 arXiv:quant-ph/0102001 . Appearances:\!

    work page doi:10.1103/physrevlett.87.167902 2001

  10. [10]

    Fernando G. S. L. Brand \ a o, Matthias Christandl, and Jon Yard. Faithful squashed entanglement. Communications in Mathematical Physics . 306(3):805--830. 2011. https://doi.org/doi:10.1007/s00220-011-1302-1 doi:doi:10.1007/s00220-011-1302-1 . STOC 2011 . https://arxiv.org/abs/1010.1750 arXiv:1010.1750 . Appearances:\!

    work page doi:10.1007/s00220-011-1302-1 2011

  11. [11]

    The complexity of stoquastic local Hamiltonian problems

    Sergey Bravyi, David P Divincenzo, Roberto Oliveira, and Barbara M Terhal. The complexity of stoquastic local Hamiltonian problems. Quantum Information & Computation . 8(5):361--385. 2008. https://doi.org/10.26421/QIC8.5-1 doi:10.26421/QIC8.5-1 . https://arxiv.org/abs/quant-ph/0606140 arXiv:quant-ph/0606140 . Appearances:\!

    work page doi:10.26421/qic8.5-1 2008

  12. [12]

    Salman Beigi. NP vs. QMA _ (2) . Quantum Information & Computation . 10(1):141--151. 2010. https://arxiv.org/abs/0810.5109 arXiv:0810.5109 . Appearances:\!

    work page arXiv 2010

  13. [13]

    Quantum Merlin--Arthur with an internally separable proof

    Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin--Arthur with an internally separable proof. arXiv preprint . 2024. https://arxiv.org/abs/2410.19152 arXiv:2410.19152 . Appearances:\!

    work page arXiv 2024

  14. [14]

    Quantum Merlin--Arthur and proofs without relative phase

    Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin--Arthur and proofs without relative phase. In Proceedings of the 15th Innovations in Theoretical Computer Science Conference ( ITCS 2024) . volume 287 of LIPIcs . pages 9:1--9:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2024. https://doi.org/10.4230/LIPICS.ITCS.2024.9 doi...

    work page doi:10.4230/lipics.itcs.2024.9 2024

  15. [15]

    In: Rovan, B., V ojt´aˇa, P

    Elmar B \"o hler, Christian Gla er, and Daniel Meister. Error-bounded probabilistic computations between MA and AM . Journal of Computer and System Sciences . 72(6):1043--1076. 2006. https://doi.org/10.1007/978-3-540-45138-9\_19 doi:10.1007/978-3-540-45138-9\_19 . MFCS 2003 . https://eccc.weizmann.ac.il/report/2003/069 ECCC:TR03-069 . Appearances:\!

    work page doi:10.1007/978-3-540-45138-9 2006

  16. [16]

    Fernando G. S. L. Brand \ a o and Aram W. Harrow. Quantum de Finetti theorems under local measurements with applications. In Proceedings of the Symposium on Theory of Computing Conference (STOC 2013) . pages 861--870. ACM . 2013. https://doi.org/10.1145/2488608.2488718 doi:10.1145/2488608.2488718 . https://arxiv.org/abs/1210.6367 arXiv:1210.6367 . Appearances:\!

    work page doi:10.1145/2488608.2488718 2013

  17. [17]

    Fernando G. S. L. Brand \ a o and Aram W. Harrow. Estimating operator norms using covering nets. arXiv preprint . 2015. https://arxiv.org/abs/1509.05065 arXiv:1509.05065 . Appearances:\!

    work page arXiv 2015

  18. [18]

    On complexity of the quantum Ising model

    Sergey Bravyi and Matthew Hastings. On complexity of the quantum Ising model. Communications in Mathematical Physics . 349(1):1--45. 2017. https://doi.org/10.1007/s00220-016-2787-4 doi:10.1007/s00220-016-2787-4 . https://arxiv.org/abs/1410.0703 arXiv:1410.0703 . Appearances:\!

    work page doi:10.1007/s00220-016-2787-4 2017

  19. [19]

    Quantum PCP s: on adaptivity, multiple provers and reductions to local H amiltonians

    Harry Buhrman, Jonas Helsen, and Jordi Weggemans. Quantum PCP s: on adaptivity, multiple provers and reductions to local H amiltonians. Quantum . 9:1791. 2025. https://doi.org/10.22331/q-2025-07-11-1791 doi:10.22331/q-2025-07-11-1791 . https://arxiv.org/abs/2403.04841 arXiv:2403.04841 . Appearances:\!

    work page doi:10.22331/q-2025-07-11-1791 2025

  20. [20]

    Kelner, and David Steurer

    Boaz Barak, Jonathan A. Kelner, and David Steurer. Rounding sum-of-squares relaxations. In Proceedings of the Symposium on Theory of Computing ( STOC 2014) . pages 31--40. ACM . 2014. https://doi.org/10.1145/2591796.2591886 doi:10.1145/2591796.2591886 . https://arxiv.org/abs/1312.6652 arXiv:1312.6652 . Appearances:\!

    work page doi:10.1145/2591796.2591886 2014

  21. [21]

    Kothari, and David Steurer

    Boaz Barak, Pravesh K. Kothari, and David Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) . pages 975--988. ACM . 2017. https://doi.org/10.1145/3055399.3055488 doi:10.1145/3055399.3055488 . https://arxiv.org/abs/1701.06321 arXiv:1701.06321...

    work page doi:10.1145/3055399.3055488 2017

  22. [22]

    Monte Carlo simulation of stoquastic hamiltonians

    Sergey Bravyi. Monte Carlo simulation of stoquastic hamiltonians. Quantum Information & Computation . 15(13-14):1122--1140. 2015. https://doi.org/10.26421/qic15.13-14-3 doi:10.26421/qic15.13-14-3 . https://arxiv.org/abs/1402.2295 arXiv:1402.2295 . Appearances:\!

    work page doi:10.26421/qic15.13-14-3 2015

  23. [23]

    2010 , journal =

    Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free Hamiltonians . SIAM Journal on Computing . 39(4):1462--1485. 2010. https://doi.org/10.1137/08072689X doi:10.1137/08072689X . https://arxiv.org/abs/0806.1746 arXiv:0806.1746 . Appearances:\!

    work page doi:10.1137/08072689x 2010

  24. [24]

    A quantum characterization of NP

    Hugue Blier and Alain Tapp. A quantum characterization of NP . computational complexity . 21(3):499--510. 2012. https://doi.org/10.1007/S00037-011-0016-2 doi:10.1007/S00037-011-0016-2 . ICQNM 2009 . https://arxiv.org/abs/0709.0738 arXiv:0709.0738 . Appearances:\!

    work page doi:10.1007/s00037-011-0016-2 2012

  25. [25]

    Cl \' e ment L. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys. Theory of Computing Library. 2020. URL: http://www.theoryofcomputing.org/library.html. https://doi.org/10.4086/toc.gs.2020.009 doi:10.4086/toc.gs.2020.009 . Appearances:\!

    work page doi:10.4086/toc.gs.2020.009 2020

  26. [26]

    Quantum meets the minimum circuit size problem

    Nai - Hui Chia, Chi - Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum meets the minimum circuit size problem. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference ( ITCS 2022) . LIPIcs. pages 47:1--47:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2022. https://doi.org/10.4230/LIPICS.ITCS.2022.47 doi:10.4230/LIP...

    work page doi:10.4230/lipics.itcs.2022.47 2022

  27. [27]

    Short multi-prover quantum proofs for SAT without entangled measurements

    Jing Chen and Andrew Drucker. Short multi-prover quantum proofs for SAT without entangled measurements. arXiv preprint . 2010. https://arxiv.org/abs/1011.0716 arXiv:1011.0716 . Appearances:\!

    work page arXiv 2010

  28. [28]

    Alessandro Chiesa and Michael A. Forbes. Improved soundness for QMA with multiple provers. Chicago Journal of Theoretical Computer Science . 2013(1). 2013. https://doi.org/10.4086/cjtcs.2013.001 doi:10.4086/cjtcs.2013.001 . Appearances:\!

    work page doi:10.4086/cjtcs.2013.001 2013

  29. [29]

    Complexity Classification of Local Hamiltonian Problems

    Toby Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems. SIAM Journal on Computing . 45(2):268--316. 2016. https://doi.org/10.1137/140998287 doi:10.1137/140998287 . FOCS 2014 . https://arxiv.org/abs/1311.3161 arXiv:1311.3161 . Appearances:\!

    work page doi:10.1137/140998287 2016

  30. [30]

    New approaches to complexity via quantum graphs

    Eric Culf and Arthur Mehta. New approaches to complexity via quantum graphs. Quantum Information & Computation . 25(5):453--487. 2025. https://doi.org/10.2478/qic-2025-0026 doi:10.2478/qic-2025-0026 . https://arxiv.org/abs/2309.12887 arXiv:2309.12887 . Appearances:\!

    work page doi:10.2478/qic-2025-0026 2025

  31. [31]

    Fomin and Petr A

    Cl \'e ment Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data. In International Colloquium on Automata, Languages, and Programming . pages 283--295. Springer. 2014. https://doi.org/10.1007/978-3-662-43948-7\_24 doi:10.1007/978-3-662-43948-7\_24 . https://arxiv.org/abs/1402.3835 arXiv:1402.3835 . Appearances:\!

    work page doi:10.1007/978-3-662-43948-7 2014

  32. [32]

    The complexity of the separable H amiltonian problem

    Andr \'e Chailloux and Or Sattath. The complexity of the separable H amiltonian problem. In Proceedings of the IEEE 27th Conference on Computational Complexity (CCC 2012) . pages 32--41. 2012. https://doi.org/10.1109/CCC.2012.42 doi:10.1109/CCC.2012.42 . Appearances:\!

    work page doi:10.1109/ccc.2012.42 2012

  33. [33]

    Sample-optimal identity testing with high probability

    Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing with high probability. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) . pages 41--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik. 2018. https://doi.org/10.4230/LIPIcs.ICALP.2018.41 doi:10.42...

    work page doi:10.4230/lipics.icalp.2018.41 2018

  34. [34]

    Exponential time complexity of the permanent and the Tutte polynomial

    Holger Dell, Thore Husfeldt, D \' a niel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms . 10(4):21:1--21:32. 2014. https://doi.org/10.1145/2635812 doi:10.1145/2635812 . ICALP 2010 . https://arxiv.org/abs/1206.1775 arXiv:1206.1775 . Appearances:\!

    work page doi:10.1145/2635812 2014

  35. [35]

    The pcp theorem by gap amplification

    Irit Dinur. The pcp theorem by gap amplification. J. ACM . 54(3):12–es. June 2007. https://doi.org/10.1145/1236457.1236459 doi:10.1145/1236457.1236459 . Appearances:\!

    work page doi:10.1145/1236457.1236459 2007

  36. [36]

    Doherty, Pablo A

    Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. Complete family of separability criteria. Physical Review A . 69(2):022308. 2004. https://doi.org/10.1103/PhysRevA.69.022308 doi:10.1103/PhysRevA.69.022308 . https://arxiv.org/abs/quant-ph/0308032 arXiv:quant-ph/0308032 . Appearances:\!

    work page doi:10.1103/physreva.69.022308 2004

  37. [37]

    The sum-of-squares hierarchy on the sphere, and applications in quantum information theory

    Kun Fang and Hamza Fawzi. The sum-of-squares hierarchy on the sphere, and applications in quantum information theory. Mathematical Programming . 190(1--2):331--360. 2021. https://doi.org/10.1007/s10107-020-01537-7 doi:10.1007/s10107-020-01537-7 . https://arxiv.org/abs/1908.05155 arXiv:1908.05155 . Appearances:\!

    work page doi:10.1007/s10107-020-01537-7 2021

  38. [38]

    Quantum Merlin--Arthur with exponentially small gap

    Bill Fefferman and Cedric Lin. Quantum Merlin--Arthur with exponentially small gap. arXiv preprint . 2016. https://arxiv.org/abs/1601.01975 arXiv:1601.01975 . Appearances:\!

    work page arXiv 2016

  39. [39]

    A complete characterization of unitary quantum space

    Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) . volume 94. page 4. 2018. https://doi.org/10.4230/LIPIcs.ITCS.2018.4 doi:10.4230/LIPIcs.ITCS.2018.4 . https://arxiv.org/abs/1604.01384 arXiv:1604.01384 . Appearances:\!

    work page doi:10.4230/lipics.itcs.2018.4 2018

  40. [40]

    The theory of matrices

    Feliks Ruvimovich Gantmakher. The theory of matrices . volume 131. American Mathematical Society. 2000. Appearances:\!

    2000

  41. [41]

    Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde. Quantum interactive proofs and the complexity of separability testing. Theory of Computing . 11(3):59--103. 2015. https://doi.org/10.4086/toc.2015.v011a003 doi:10.4086/toc.2015.v011a003 . https://arxiv.org/abs/1308.5788 arXiv:1308.5788 . Appearances:\!

    work page doi:10.4086/toc.2015.v011a003 2015

  42. [42]

    Hastings, and Umesh V

    Andr \' a s Gily \' e n, Matthew B. Hastings, and Umesh V. Vazirani. (sub)exponential advantage of adiabatic quantum computation with no sign problem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021) . pages 1357--1369. ACM . 2021. https://doi.org/10.1145/3406325.3451060 doi:10.1145/3406325.3451060 . https://arxiv....

    work page doi:10.1145/3406325.3451060 2021

  43. [43]

    On the complexity of estimating ground state entanglement and free energy

    Sevag Gharibian and Jonas Kamminga. On the complexity of estimating ground state entanglement and free energy. arXiv preprint . 2025. https://arxiv.org/abs/2510.06796 arXiv:2510.06796 . Appearances:\!

    work page arXiv 2025

  44. [44]

    Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum PCP conjecture

    Sevag Gharibian and Fran c ois Le Gall . Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum PCP conjecture. SIAM Journal on Computing . 52(4):1009--1038. 2023. https://doi.org/10.1137/22M1513721 doi:10.1137/22M1513721 . STOC 2022 . https://arxiv.org/abs/2111.09079 arXiv:2111.09079 . Appea...

    work page doi:10.1137/22m1513721 2023

  45. [45]

    On the pure quantum polynomial hierarchy and quantified Hamiltonian complexity

    Sabee Grewal and Dorian Rudolph. On the pure quantum polynomial hierarchy and quantified Hamiltonian complexity. arXiv preprint . 2025. https://arxiv.org/abs/2510.06522 arXiv:2510.06522 . Appearances:\!

    work page arXiv 2025

  46. [46]

    Private coins versus public coins in interactive proof systems

    Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Advances in Computing Research . 5:73--90. 1989. https://doi.org/doi.org/10.1145/12130.12137 doi:doi.org/10.1145/12130.12137 . STOC 1986 . Appearances:\!

    work page doi:10.1145/12130.12137 1989

  47. [47]

    Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

    Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2) . computational complexity . 31(2):1--52. 2022. MFCS 2018 . https://arxiv.org/abs/1805.11139 arXiv:1805.11139 . Appearances:\!

    work page arXiv 2022

  48. [48]

    QMA variants with polynomially many provers

    Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay. QMA variants with polynomially many provers. Quantum Information & Computation . 13(1-2):135--157. 2013. https://doi.org/10.26421/QIC13.1-2-8 doi:10.26421/QIC13.1-2-8 . https://arxiv.org/abs/1108.0617 arXiv:1108.0617 . Appearances:\!

    work page doi:10.26421/qic13.1-2-8 2013

  49. [49]

    , TITLE =

    Philip Hall. On representatives of subsets. Journal of the London Mathematical Society . s1-10(1):26--30. 1935. https://doi.org/10.1112/jlms/s1-10.37.26 doi:10.1112/jlms/s1-10.37.26 . Appearances:\!

    work page doi:10.1112/jlms/s1-10.37.26 1935

  50. [50]

    The Power of Adiabatic Quantum Computation with No Sign Problem

    Matthew B. Hastings. The power of adiabatic quantum computation with no sign problem. Quantum . 5:597. 2021. https://doi.org/10.22331/q-2021-12-06-597 doi:10.22331/q-2021-12-06-597 . https://arxiv.org/abs/2005.03791 arXiv:2005.03791 . Appearances:\!

    work page doi:10.22331/q-2021-12-06-597 2021

  51. [51]

    Dequantization barriers for guided stoquastic Hamiltonians

    Yassine Hamoudi, Yvan Le Borgne, and Shrinidhi Teganahally Sridhara. Dequantization barriers for guided stoquastic Hamiltonians . arXiv preprint arXiv:2602.23183 . 2026. Appearances:\!

    work page arXiv 2026

  52. [52]

    Computational complexity of the homology problem with orientable filtration: MA -completeness

    Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, and Vedran Dunjko. Computational complexity of the homology problem with orientable filtration: MA -completeness. arXiv preprint . 2025. https://arxiv.org/abs/2510.07014 arXiv:2510.07014 . Appearances:\!

    work page arXiv 2025

  53. [53]

    ubener, Matthias Kleinmann, Tzu-Chieh Wei, Carlos Gonz\'alez-Guill\'en, and Otfried G\

    Robert H\"ubener, Matthias Kleinmann, Tzu-Chieh Wei, Carlos Gonz\'alez-Guill\'en, and Otfried G\"uhne. Geometric measure of entanglement for symmetric states. Physics Review A . 80:032324. 2009. https://doi.org/10.1103/PhysRevA.80.032324 doi:10.1103/PhysRevA.80.032324 . https://arxiv.org/abs/0905.4822 arXiv:0905.4822 . Appearances:\!

    work page doi:10.1103/physreva.80.032324 2009

  54. [54]

    Testing product states, quantum Merlin--Arthur games and tensor optimization

    Aram W Harrow and Ashley Montanaro. Testing product states, quantum Merlin--Arthur games and tensor optimization. Journal of the ACM . 60(1):1--43. 2013. FOCS 2010 . https://arxiv.org/abs/1001.0017 arXiv:1001.0017 . Appearances:\!

    work page arXiv 2013

  55. [55]

    An improved semidefinite programming hierarchy for testing entanglement

    Aram W Harrow, Anand Natarajan, and Xiaodi Wu. An improved semidefinite programming hierarchy for testing entanglement. Communications in Mathematical Physics . 352(3):881--904. 2017. https://doi.org/10.1007/s00220-017-2859-0 doi:10.1007/s00220-017-2859-0 . https://arxiv.org/abs/1506.08834 arXiv:1506.08834 . Appearances:\!

    work page doi:10.1007/s00220-017-2859-0 2017

  56. [56]

    Termwise versus globally stoquastic local hamiltonians: questions of complexity and sign-curing,

    Marios Ioannou, Stephen Piddock, Milad Marvian, Joel Klassen, and Barbara M Terhal. Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing. arXiv preprint . 2020. https://arxiv.org/abs/2007.11964 arXiv:2007.11964 . Appearances:\!

    work page arXiv 2020

  57. [57]

    Counting, Sampling and Integrating: Algorithms and Complexity

    Mark Jerrum. Counting, Sampling and Integrating: Algorithms and Complexity . Lectures in Mathematics. ETH Z\"urich. Springer Basel AG. 1st edition. 2003. https://doi.org/10.1007/978-3-0348-8005-3 doi:10.1007/978-3-0348-8005-3 . Appearances:\!

    work page doi:10.1007/978-3-0348-8005-3 2003

  58. [58]

    Local Hamiltonian Problem with Succinct Ground State is MA-Complete

    Jiaqing Jiang. Local hamiltonian problem with succinct ground state is MA -complete. PRX Quantum . 6(2):020312. 2025. https://doi.org/10.1103/PRXQuantum.6.020312 doi:10.1103/PRXQuantum.6.020312 . https://arxiv.org/abs/2309.10155 arXiv:2309.10155 . Appearances:\!

    work page doi:10.1103/prxquantum.6.020312 2025

  59. [59]

    The QMA(2) universe: Complexity, entanglement, and optimization

    Fernando Granha Jeronimo, Itai Leigh, and Pei Wu. The QMA(2) universe: Complexity, entanglement, and optimization. ACM SIGACT News . 57(1):64--99. 2026. https://doi.org/10.1145/3802807.3802814 doi:10.1145/3802807.3802814 . Appearances:\!

    work page doi:10.1145/3802807.3802814 2026

  60. [60]

    Completely positive completely positive maps (and a resource theory for non-negativity of quantum amplitudes)

    Nathaniel Johnston and Jamie Sikora. Completely positive completely positive maps (and a resource theory for non-negativity of quantum amplitudes). Linear Algebra and its Applications . 653:395--429. 2022. https://doi.org/10.1016/j.laa.2022.08.016 doi:10.1016/j.laa.2022.08.016 . https://arxiv.org/abs/2110.13568 arXiv:2110.13568 . Appearances:\!

    work page doi:10.1016/j.laa.2022.08.016 2022

  61. [61]

    The power of unentangled quantum proofs with non-negative amplitudes

    Fernando Granha Jeronimo and Pei Wu. The power of unentangled quantum proofs with non-negative amplitudes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing ( STOC 2023) . pages 1629--1642. ACM . 2023. https://doi.org/10.1145/3564246.3585248 doi:10.1145/3564246.3585248 . https://arxiv.org/abs/2402.18790 arXiv:2402.18790 . Appearances:\!

    work page doi:10.1145/3564246.3585248 2023

  62. [62]

    Dimension independent disentanglers from unentanglement and applications

    Fernando Granha Jeronimo and Pei Wu. Dimension independent disentanglers from unentanglement and applications. In Proceedings of the 39th Computational Complexity Conference ( CCC 2024) . volume 300 of LIPIcs . pages 26:1--26:28. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2024. https://doi.org/10.4230/LIPICS.CCC.2024.26 doi:10.4230/LIPICS.CCC...

    work page doi:10.4230/lipics.ccc.2024.26 2024

  63. [63]

    Quantum NP

    Alexei Kitaev. Quantum NP . Public Talk at AQIP'99: the 2nd Workshop on Algorithms in Quantum Information Processing . 1999. Appearances:\!

    1999

  64. [64]

    Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, and Barbara M. Terhal. Hardness and ease of curing the sign problem for two-local qubit hamiltonians. SIAM Journal on Computing . 49(6):1332--1362. 2020. https://doi.org/10.1137/19M1287511 doi:10.1137/19M1287511 . https://arxiv.org/abs/1906.08800 arXiv:1906.08800 . Appearances:\!

    work page doi:10.1137/19m1287511 2020

  65. [65]

    Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur ? Chicago Journal of Theoretical Computer Science

    Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur ? Chicago Journal of Theoretical Computer Science . 2009:3. 2009. ISACC 2003 . https://arxiv.org/abs/quant-ph/0306051 arXiv:quant-ph/0306051 . Appearances:\!

    work page arXiv 2009

  66. [66]

    Non-interactive quantum perfect and statistical zero-knowledge

    Hirotada Kobayashi. Non-interactive quantum perfect and statistical zero-knowledge. In Proceedings of the 14th International Symposium on Algorithms and Computation . pages 178--188. Springer. 2003. https://doi.org/10.1007/978-3-540-24587-2\_20 doi:10.1007/978-3-540-24587-2\_20 . https://arxiv.org/abs/quant-ph/0207158 arXiv:quant-ph/0207158 . Appearances:\!

    work page doi:10.1007/978-3-540-24587-2 2003

  67. [67]

    The pure-state consistency of local density matrices problem: In PSPACE and complete for a class between QMA and QMA(2)

    Jonas Kamminga and Dorian Rudolph. The pure-state consistency of local density matrices problem: In PSPACE and complete for a class between QMA and QMA(2) . In Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) . LIPIcs. pages 83:1--83:23. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2026. https://doi.org...

    work page doi:10.4230/lipics.itcs.2026.83 2026

  68. [68]

    Kitaev, Alexander H

    Alexei Y. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation . volume 47 of Graduate Studies in Mathematics . American Mathematical Society. 1st edition. 2002. https://doi.org/10.1090/gsm/047/08 doi:10.1090/gsm/047/08 . Appearances:\!

    work page doi:10.1090/gsm/047/08 2002

  69. [69]

    Joel Klassen and Barbara M. Terhal. Two-local qubit H amiltonians: when are they stoquastic? Quantum . 3:139. 2019. https://doi.org/10.22331/q-2019-05-06-139 doi:10.22331/q-2019-05-06-139 . https://arxiv.org/abs/1806.05405 arXiv:1806.05405 . Appearances:\!

    work page doi:10.22331/q-2019-05-06-139 2019

  70. [70]

    How hard is it to approximate the Jones polynomial? Theory of Computing

    Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing . 11(1):183--219. 2015. https://doi.org/10.4086/toc.2015.v011a006 doi:10.4086/toc.2015.v011a006 . https://arxiv.org/abs/0908.0512 arXiv:0908.0512 . Appearances:\!

    work page doi:10.4086/toc.2015.v011a006 2015

  71. [71]

    Klivans and Dieter van Melkebeek

    Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing . 31(5):1501--1526. 2002. https://doi.org/10.1137/S0097539700389652 doi:10.1137/S0097539700389652 . STOC 1999 . https://eccc.weizmann.ac.il/report/1998/075 ECCC:TR98-075 . Appearances:\!

    work page doi:10.1137/s0097539700389652 2002

  72. [72]

    Classical algorithms for constant approximation of the ground state energy of local Hamiltonians

    Fran c ois Le Gall. Classical algorithms for constant approximation of the ground state energy of local Hamiltonians . In Proceedings of the 33rd Annual European Symposium on Algorithms ( ESA 2025) . LIPIcs. pages 73:1--73:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2025. https://doi.org/10.4230/LIPICS.ESA.2025.73 doi:10.4230/LIPICS.ESA.20...

    work page doi:10.4230/lipics.esa.2025.73 2025

  73. [73]

    The local consistency problem for stoquastic and 1-D quantum systems

    Yi-Kai Liu. The local consistency problem for stoquastic and 1-D quantum systems. arXiv preprint . 2007. https://arxiv.org/abs/0712.1388 arXiv:0712.1388 . Appearances:\!

    work page arXiv 2007

  74. [74]

    StoqMA Meets Distribution Testing

    Yupan Liu. StoqMA meets distribution testing. In Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) . volume 197 of Leibniz International Proceedings in Informatics (LIPIcs) . pages 4:1--4:22. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik. 2021. https://doi.org/10.4230/LIPIcs.TQC.202...

    work page doi:10.4230/lipics.tqc.2021.4 2021

  75. [75]

    On QMA protocols with two short quantum proofs

    Fran c ois Le Gall , Shota Nakagawa, and Harumichi Nishimura. On QMA protocols with two short quantum proofs. Quantum Information & Computation . 12(7--8):589--600. 2012. https://doi.org/10.26421/QIC12.7-8-4 doi:10.26421/QIC12.7-8-4 . Appearances:\!

    work page doi:10.26421/qic12.7-8-4 2012

  76. [76]

    Quantum de Finetti theorem under fully-one-way adaptive measurements

    Ke Li and Graeme Smith. Quantum de Finetti theorem under fully-one-way adaptive measurements. Physical review letters . 114(16):160503. 2015. https://doi.org/10.1103/PhysRevLett.114.160503 doi:10.1103/PhysRevLett.114.160503 . https://arxiv.org/abs/1408.6829 arXiv:1408.6829 . Appearances:\!

    work page doi:10.1103/physrevlett.114.160503 2015

  77. [77]

    Flexible constrained de Finetti reductions and applications

    C \'e cilia Lancien and Andreas Winter. Flexible constrained de Finetti reductions and applications. Journal of Mathematical Physics . 58(9). 2017. https://doi.org/10.1063/1.5003633 doi:10.1063/1.5003633 . https://arxiv.org/abs/1605.09013 arXiv:1605.09013 . Appearances:\!

    work page doi:10.1063/1.5003633 2017

  78. [78]

    A complexity phase transition at the EPR Hamiltonian

    Kunal Marwaha and James Sud. A complexity phase transition at the EPR Hamiltonian . arXiv preprint . 2026. https://arxiv.org/abs/2604.13026 arXiv:2604.13026 . Appearances:\!

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  79. [79]

    Derandomizing Arthur--Merlin games using hitting sets

    Peter Bro Miltersen and N Variyam Vinodchandran. Derandomizing Arthur--Merlin games using hitting sets. computational complexity . 14(3):256--279. 2005. https://doi.org/10.1007/s00037-005-0197-7 doi:10.1007/s00037-005-0197-7 . FOCS 1999 . Appearances:\!

    work page doi:10.1007/s00037-005-0197-7 2005

  80. [80]

    Quantum Arthur--Merlin games

    Chris Marriott and John Watrous. Quantum Arthur--Merlin games. computational complexity . 14(2):122--152. 2005. https://doi.org/10.1007/s00037-005-0194-x doi:10.1007/s00037-005-0194-x . CCC 2004 . https://arxiv.org/abs/cs/0506068 arXiv:cs/0506068 . Appearances:\!

    work page doi:10.1007/s00037-005-0194-x 2005

Showing first 80 references.