Pith. sign in

REVIEW 4 major objections 3 minor 29 references

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy

T0 review · 4 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that unique quantum-classical probabilistically checkable proofs are as powerful as general ones under randomized reductions, and that a non-uniform quantum Karp–Lipton theorem plus a bounded-entanglement hierarchy…

desk verdict The UniqueQCPCP=QCPCP collapse rests on a false polynomial reduction, and the Karp–Lipton proof has a serious gap; the paper needs major revision. read the letter →

arxiv 2506.19792 v2 pith:BWMV2MXM submitted 2025-06-24 quant-ph cs.CC

Kartik Anand , Kabgyun Jeong , Junseo Lee This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1268Q1581P68 PACS 03.67.-a03.67.Lx
keywords quantumcomplexitytheoryprobabilisticallycheckableproofsuniquepolynomialhierarchyKarp-Liptontheoremboundedentanglementadviceconvexoptimization
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper sets out to show that several constraints on quantum proof systems do not constrain as much as they seem. It claims that requiring a quantum-classical PCP to have a unique accepting proof leaves its power unchanged, $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathrm{BQ}$-operator and randomized reductions. It also proves a quantum analogue of the Karp–Lipton theorem—if $\mathsf{QMA}\subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH}\subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$—and introduces a bounded-entanglement hierarchy $\mathsf{BEQPH}$ that collapses unconditionally at level four, with each level reducible to a convex optimization problem. If these results are right, the computational border between 'hard' and 'easy' quantum proof systems is not drawn by uniqueness, advice, or entanglement by itself, but by whether the feasible set of protocols is convex.

What carries the argument

The carrying objects are the $\mathrm{BQ}$-operator—a polynomial-time quantum reduction with success probability at least $2/3$—and convexity of quantum state sets. For the PCP result, the chain $\mathsf{QCPCP} \le_{\mathrm{BQ}} \mathsf{MTP} \le_p \mathsf{SAT} \le_{\mathrm{RP}} \mathsf{UniqueSAT} \le_p \mathsf{UniqueMTP} \le_{\mathrm{BQ}} \mathsf{UniqueQCPCP}$ transforms a general quantum-classical PCP into one with a unique proof, with uniqueness preserved by the Valiant–Vazirani hashing reduction. For the hierarchy results, the collapse is driven by Sion's minimax theorem applied to bilinear acceptance probabilities over convex, compact sets of density matrices with bounded relative entropy of entanglement; the consistent extension property ties each round to the previous one, and the bounded-entanglement sets $T^{(m)}$ have convex feasible regions, so alternating quantifiers reorder and every level becomes a two-round max-min problem.

What would settle it

Test the reduction on the formula $\varphi = x_1 \wedge (x_1 \vee \neg x_1)$, whose unique satisfying assignment is $x_1=1$. The lemma constructs $P(x)=x_1+x_1(1-x_1)$; at $x_1=1$, $P=1$, while the threshold is $a=m=2$, so the unique satisfying assignment is not accepted—directly contradicting the completeness condition and hence the claimed reduction chain.

Watch

Extended reading notes

Core claim

The paper's central discovery is that uniqueness and entanglement bounds do not carry the computational weight one might expect. In the PCP setting, it proves $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ by composing a $\mathrm{BQ}$ reduction from $\mathsf{QCPCP}$ to a multilinear threshold problem, a deterministic reduction to $\mathsf{SAT}$, the Valiant–Vazirani randomized reduction from $\mathsf{SAT}$ to $\mathsf{UniqueSAT}$, a deterministic reduction back to a unique multilinear threshold problem, and a $\mathrm{BQ}$ reduction from that problem to a unique quantum-classical verifier. In the hierarchy setting, it proves that the assumption $\mathsf{QMA}\subseteq \mathsf{BQP}/\mathsf{qpoly}$ forces $\mathsf{QPH}\subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$, a non-uniform quantum Karp–Lipton theorem. It then defines $\mathsf{BEQPH}$, whose proof states must satisfy a consistent extension property and an upper bound on relative entropy of entanglement, and shows that every level of $\mathsf{BEQPH}$ is equivalent to a two-round convex max-min problem, yielding an unconditional collapse $\mathsf{BEQ\Sigma}_k = \mathsf{BEQ\Sigma}_4$ for all $k\ge 4$; the zero-entanglement variant $\mathsf{SepQPH}$ inherits the same collapse. The stated reason is that the feasible sets are convex and compact, so Sion's minimax theorem lets the alternating quantifiers be reordered, whereas the product-state sets in $\mathsf{QPH}$ are non-convex.

Load-bearing premise

The reduction chain to unique quantum-classical PCPs assumes that a satisfied clause in the CNF formula contributes a full $1$ to the constructed multilinear polynomial; this is only true when every literal in the clause is true.

Editorial extensions

If this is right

  • If $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ holds, uniqueness is not a resource limitation in quantum-classical PCPs, and any hardness or completeness result for $\mathsf{QCPCP}$ carries over to its unique variant.
  • The quantum Karp–Lipton theorem implies that if QMA has efficient quantum advice, then the whole quantum polynomial hierarchy can be decided by a $\mathsf{Q\Sigma}_2$ protocol with that same advice, matching the classical $\mathsf{PH} = \mathsf{\Sigma}_2$ collapse.
  • The BEQPH collapse means that imposing bounded-entanglement and consistency constraints across rounds adds no power beyond level four; higher levels reduce to two-round convex optimization and are therefore tractable in the semidefinite-programming sense.
  • Since SepQPH with zero entanglement also collapses but cannot simulate QPH, the hardness of QPH cannot be blamed on entanglement alone—the non-convexity of product states is essential.
  • The results place BEQPH and SepQPH inside $\mathsf{QRG(1)}$, the class of constant-round quantum refereed games, and support the paper's conjecture that both are properly contained in QPH.

Reading between the lines

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

  • I infer that the convexity mechanism is generic: any entanglement measure with convex and compact sublevel sets—not just relative entropy of entanglement—should yield the same fourth-level collapse, which is testable by rerunning the proof with a different measure.
  • I infer that the UniqueQCPCP result may be repairable if the flawed polynomial encoding in Lemma 2.9 is replaced by one in which each satisfied clause contributes exactly 1, for example by summing over all subsets of literals in a clause; the rest of the reduction chain would then go through unchanged.
  • I infer that the non-uniform Karp–Lipton proof, which only invokes QMA containment at the base level, likely extends to QCMA or to classical advice, giving $\mathsf{QPH}\subseteq \mathsf{Q\Sigma}_2/\mathsf{poly}$ under the analogous assumption.
  • I infer that the inability of SepQPH to simulate QPH suggests a separation result: if SepQPH is eventually proved to be properly contained in QPH, it would pin convexity of the proof set as the exact boundary between tractable and potentially intractable quantum hierarchies.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper claims three main results. First, it argues that restricting quantum-classical probabilistically checkable proofs to unique accepting proofs does not reduce power: UniqueQCPCP = QCPCP under BQ-operator and randomized reductions, via the chain QCPCP ≤ BQ MTP ≤ p SAT ≤ RP UniqueSAT ≤ p UniqueMTP ≤ BQ UniqueQCPCP. Second, it claims a non-uniform quantum Karp-Lipton theorem: if QMA ⊆ BQP/qpoly, then QPH ⊆ QΣ2/qpoly. Third, it introduces bounded-entanglement and separable variants BEQPH and SepQPH, claims that each level reduces to a two-round convex optimization problem, and that BEQPH (and SepQPH) collapse above the fourth level. The paper is clearly structured and credits prior work on QPCP reductions, the Valiant-Vazirani theorem, and the collapse of QEPH, but the central arguments contain serious technical flaws.

Significance. If correct, the results would be substantial: a uniqueness collapse for quantum-classical PCPs, a non-uniform Karp-Lipton statement with quantum advice, and a new family of tractable hierarchy variants. The paper also has useful expository elements, such as the explicit reduction-chain diagram and the separation of convexity-based collapse mechanisms from entanglement-based ones. However, the main claims are not established. The reduction in Lemma 2.9 is mathematically incorrect, the Karp-Lipton proof applies QMA to promise problems with quantum inputs, and the proof invokes QΣ2 = QΠ2 without justification. The BEQPH collapse argument also uses a minimax swap that does not follow from Sion's theorem. Since these are load-bearing defects in all three advertised contributions, the paper cannot be accepted in its present form.

major comments (4)
  1. [Section 2.2, Lemma 2.9, Eqs. (2.6)-(2.7) and Eq. (2.13)] Lemma 2.9 is false. The polynomial P(x) = Σ_j ∏_{ℓ∈C_j} x̃_ℓ, with x̃_ℓ = x_i for ℓ = x_i and x̃_ℓ = 1−x_i for ℓ = ¬x_i, evaluates to 1 on a clause only when every literal in that clause is true, not when the clause is merely satisfied. A satisfying assignment can therefore have P(x) < m. For example, φ = (x1∨x2) ∧ (¬x1) has the unique satisfying assignment (0,1), but P(0,1) = x1x2 + (1−x1) = 0 + 1 = 1 < 2 = m. Thus this UniqueSAT YES instance is mapped to a UniqueMTP NO instance. Since Lemma 2.9 is the UniqueSAT-to-UniqueMTP link in the composition (2.13) used in Theorem 2.11, the claimed collapse UniqueQCPCP = QCPCP is unsupported.
  2. [Section 3.2, Theorem 3.10, Eqs. (3.9)-(3.12)] The base case of the Karp-Lipton proof defines a promise problem P_x whose inputs are the quantum states (ρ1,ρ2), and then asserts 'By construction, P_x ∈ QMA.' This is not standard QMA: QMA is a class of promise problems over classical bit strings, with a quantum witness supplied to the verifier, not a class of problems whose instance itself is a quantum state. A circuit receiving x, ρ1, ρ2, and an advice state is not a QMA verifier for a classical language. The same issue appears in the inductive step at Eqs. (3.16)-(3.18), where the supposed language A' has inputs (x,ρ1,ρ2) containing quantum states. The assumption QMA ⊆ BQP/qpoly therefore cannot be applied as written.
  3. [Section 3.2, Theorem 3.10, Eqs. (3.20)-(3.21)] The proof uses the equalities QΣ2 = QΠ2 and QΠ2/qpoly = QΣ2/qpoly as if they were available. The paper does not prove these equalities, and they are not known consequences of the stated definitions; QΣ2 = QΠ2 is itself a collapse statement at the second level of QPH. Using it in a proof that QPH ⊆ QΣ2/qpoly is either circular or relies on an unproven assumption. This step is load-bearing, since it is what reduces the inner quantifier block ∀ρ2∃σ1∀σ2 to a QΣ2/qpoly predicate in the induction step.
  4. [Section 3.3, Theorem 3.14, Eqs. (3.25)-(3.28)] The collapse argument for BEQPH does not justify its minimax swap. The expression v*3 = max_{ρ1} min_{σ1} max_{ρ2∈S(ρ1)} Tr(R(ρ2⊗σ1)) is rewritten as max over a joint set of (ρ1,ρ2) followed by min over σ1, with the explanation that Sion's theorem applies. Sion's theorem swaps an outer max and min over convex compact sets for a function that is concave-convex in the two variables. Here the inner max over ρ2 is constrained by ρ1, so the two quantifiers being interchanged are not over an independent product set. Convexity of S(ρ1) does not by itself permit moving the max over ρ2 past the intervening min over σ1. Consequently the reduction of BEQΣ3 to Eq. (3.28), and the analogous derivation for BEQΣ4 and higher levels, is not established.
minor comments (3)
  1. [Section 2.2, Lemma 2.8] The proof states a 'standard promise structure' whose first condition is 'There exists at least a y such that P(y) ≥ a' and whose second condition is 'For all y, P(y) < a'; these two conditions cannot both be part of the same promise. The YES and NO cases should be stated disjunctively and should match Definition 2.2.
  2. [Section 2.2, Lemma 2.10, step (i)] Sampling a uniform real r ∈ [0,B) using ⌈log n⌉ random bits is impossible, since a finite number of bits cannot sample a continuous uniform distribution. The proof should specify a fixed-point precision and argue that the gap δD is preserved.
  3. [Section 3.3, Definition 3.12] The sentence containing 'where b_{i−1} < B_{i−1}' is notationally unclear: B_{i−1} is not defined, and the use of B for both a prover register and an entanglement bound is confusing. Please define the maximal entanglement quantity explicitly and use distinct notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: the collapsed claims are assembled from external reductions and structural arguments rather than from fitted parameters or self-referential definitions.

full rationale

The paper's derivation chain is not circular in the sense used by this pass. The central claim UniqueQCPCP = QCPCP is obtained by composing the external reduction QCPCP ≤_BQ MTP from [BGW24], a deterministic MTP-to-SAT encoding (Lemma 2.8), the classical Valiant-Vazirani randomized reduction from [VV86], a UniqueSAT-to-UniqueMTP construction (Lemma 2.9), and a UniqueMTP-to-UniqueQCPCP verifier construction (Lemma 2.10). None of these steps fits a parameter to the equality being proved, renames the conclusion as an input, or introduces the target result as an assumption. The non-uniform Karp-Lipton collapse is a conditional statement proved by induction over quantifier blocks, with QMA ⊆ BQP/qpoly as the hypothesis, and the BEQPH/SepQPH collapses are derived from Sion's minimax theorem and the convexity of the feasible sets. There is no load-bearing self-citation: the cited works [BGW24], [VV86], [GY24], and [INN+22] are external to the authors of this paper. The most visible technical concern is Lemma 2.9, whose claim that a satisfied clause forces the monomial product to equal 1 is mathematically incorrect; however, that is a soundness/correctness flaw rather than a circularity, because the reduction does not presuppose its own conclusion. The proof also invokes the equality QΣ2 = QΠ2 without a proof at equations (3.20)-(3.21), which is a missing justification rather than a circular step. Under the circularity rubric, which requires exhibiting a specific reduction of a claimed result to its own inputs, the paper receives a score of zero.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The paper rests on standard external theorems (Valiant-Vazirani, Sion, Krein-Milman) plus several unproven or false premises. Most damaging are the false UniqueSAT-to-UniqueMTP reduction and the unjustified QΣ2=QΠ2 equality.

assumptions (4)
  • ad hoc to paper The polynomial P(x)=Σ_{j=1}^m ∏_{ℓ∈C_j} x̃_ℓ counts the number of satisfied clauses for an assignment x.
    Invoked in Lemma 2.9; false because a clause is satisfied if at least one literal is true, but the product over all literals is 1 only if every literal in the clause is true.
  • domain assumption QMA verifiers can accept quantum states as inputs, so the inner problem P_x in the Karp-Lipton proof is in QMA.
    Used in Theorem 3.10 base case; QMA is defined for classical inputs, so substituting quantum states (ρ1,ρ2) as inputs is outside the standard definition and the assumption QMA⊆BQP/qpoly does not apply.
  • ad hoc to paper QΣ2 = QΠ2 in the quantum polynomial hierarchy.
    Used in Theorem 3.10 inductive step to conclude QΠ3/qpoly ⊆ QΣ2/qpoly; this equality is not known and would itself be a collapse of QPH.
  • standard math Sion's minimax theorem applies to the feasible sets of BEQPH across all rounds.
    Used in Theorem 3.14; requires convexity and compactness of the sets T^{(m)}. Relative entropy of entanglement sublevel sets are convex, but the proof that the merged sets behave as claimed is sketchy.
invented entities (2)
  • BEQPH (bounded-entanglement quantum polynomial hierarchy)
    purpose: Define a variant of QPH with consistent extensions and bounded relative entropy of entanglement that collapses to the fourth level.
    A new complexity class defined in the paper; its utility depends on the correctness of the collapse proof, which is not fully established.
  • SepQPH (separable quantum polynomial hierarchy)
    purpose: Define the zero-entanglement limit of BEQPH, claimed to collapse to the fourth level and to separate from QPH.
    A new complexity class defined in the paper; the separation from QPH is argued from convexity but not rigorously proven.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy." pith.science (2026). https://pith.science/paper/BWMV2MXM

@misc{pith2026250619792,
  author       = {Pith},
  title        = {Pith review of: Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BWMV2MXM}},
  note         = {Machine review of arXiv:2506.19792}
}
abstract

We investigate the structure of quantum proof systems by establishing collapse results that reveal simplifications in their complexity landscape. By extending classical theorems such as the Karp-Lipton theorem to quantum settings and analyzing uniqueness in quantum-classical PCPs, we clarify how various constraints influence computational power. Our main contributions are: (1) We show that restricting quantum-classical PCPs to unique proofs does not reduce their power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions. This parallels the known $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result, indicating robustness of uniqueness even in quantum PCP-type systems. (2) We prove a non-uniform quantum analogue of the Karp-Lipton theorem: if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$. This conditional collapse suggests limits on quantum advice for $\mathsf{QMA}$-complete problems. (3) We define a bounded-entanglement version of the quantum polynomial hierarchy, $\mathsf{BEQPH}$, and prove that it collapses above the fourth level. We also introduce the separable hierarchy $\mathsf{SepQPH}$ (zero entanglement), for which the same collapse result holds. These collapses stem not from entanglement, as in prior work, but from the convex structure of the protocols, which renders higher levels tractable. Collectively, these results offer new insights into the structure of quantum proof systems and the role of entanglement, uniqueness, and advice in defining their complexity.

Figures

Figures reproduced from arXiv: 2506.19792 by the authors.

Figure 1
Figure 1. Reduction structure used to prove the collapse result UniqueQCPCP = QCPCP. The left side illustrates the original reduction chain from QCPCP, as established in [BGW24]. The right side depicts our refined reduction path to the unique variant, culminating in UniqueQCPCP (Definition 2.1). Key components include deterministic and randomized reductions, as well as the application of the BQ-operator. Proof. Let P(y) denot… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 24 canonical work pages

  1. [1]

    Quantum hamiltonian complexity and the detectability lemma

    Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. Quantum hamiltonian complexity and the detectability lemma. arXiv:1011.3445 , 2010

    arXiv 2010

  2. [2]

    The complexity of quantum states and transformations: From quantum money to black holes

    Scott Aaronson. The complexity of quantum states and transformations: From quantum money to black holes. arXiv:1607.05256 , 2016

    arXiv 2016

  3. [3]

    Brand \ a o, and Or Sattath

    Dorit Aharonov, Michael Ben-Or, Fernando G.S.L. Brand \ a o, and Or Sattath. The P ursuit of U niqueness: E xtending V aliant- V azirani T heorem to the P robabilistic and Q uantum S ettings. Quantum , 6, March 2022

    work page 2022

  4. [4]

    Quantum polynomial hierarchies: Karp-lipton, error reduction, and lower bounds

    Avantika Agarwal, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. Quantum polynomial hierarchies: Karp-lipton, error reduction, and lower bounds. In 49th International Symposium on Mathematical Foundations of Computer Science , 2024

    work page 2024

  5. [5]

    Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T. Nguyen. Uniqueqma vs qma: oracle separation and eigenstate thermalization hypothesis. arXiv:2410.23811 , 2024

    work page arXiv 2024

  6. [6]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM , 45(3), 1998

    work page 1998

  7. [7]

    Trading group theory for randomness

    L \'a szl \'o Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , 1985

    work page 1985

  8. [8]

    Non-deterministic exponential time has two-prover interactive protocols

    L \'a szl \'o Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity , 1, 1991

    work page 1991

Show all 29 references
  1. [9]

    Classical versus quantum queries in quantum pcps with classical proofs

    Harry Buhrman, Fran c ois Le Gall, and Jordi Weggemans. Classical versus quantum queries in quantum pcps with classical proofs. arXiv:2411.00946 , 2024

    2024 arXiv

  2. [10]

    Quantum pcps: on adaptivity, multiple provers and reductions to local hamiltonians

    Harry Buhrman, Jonas Helsen, and Jordi Weggemans. Quantum pcps: on adaptivity, multiple provers and reductions to local hamiltonians. arXiv:2403.04841 , 2024

    2024 arXiv

  3. [11]

    Interactive proofs and the hardness of approximating cliques

    Uriel Feige, Shafi Goldwasser, Laszlo Lov\' a sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM , 43(2), 1996

    1996

  4. [12]

    A collapsible polynomial hierarchy for promise problems

    Chirag Falor, Shu Ge, and Anand Natarajan. A collapsible polynomial hierarchy for promise problems. arXiv:2311.12228 , 2023

    2023 arXiv

  5. [13]

    Hardness of approximation for quantum problems

    Sevag Gharibian and Julia Kempe. Hardness of approximation for quantum problems. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming . Springer Berlin Heidelberg, 2012

    2012

  6. [14]

    The knowledge complexity of interactive proof-systems

    Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , 1985

    1985

  7. [15]

    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, 09 2022

    2022

  8. [16]

    The entangled quantum polynomial hierarchy collapses

    Sabee Grewal and Justin Yirka. The entangled quantum polynomial hierarchy collapses. In 39th Computational Complexity Conference , volume 300, 2024

    2024

  9. [17]

    Quantum search-to-decision reductions and the state synthesis problem

    Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem. In 37th Computational Complexity Conference , 2022

    2022

  10. [18]

    Mip* = re

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Mip* = re. Communications of the ACM , 64(11), 2021

    2021

  11. [19]

    Parallel approximation of non-interactive zero-sum quantum games

    Rahul Jain and John Watrous. Parallel approximation of non-interactive zero-sum quantum games. In 24th Annual IEEE Conference on Computational Complexity , 2009

    2009

  12. [20]

    Karp and Richard J

    Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing , 1980

    1980

  13. [21]

    González Guillén

    Joshua Lockhart and Carlos E. González Guillén. Quantum state isomorphism. arXiv:1709.09622 , 2017

    2017 arXiv

  14. [22]

    Milman M

    D. Milman M. Krein. On extreme points of regular convex sets. Studia Mathematica , 9(1), 1940

    1940

  15. [23]

    A parallel repetition theorem

    Ran Raz. A parallel repetition theorem. SIAM Journal on Computing , 27(3), 1998

    1998

  16. [24]

    Ip = pspace

    Adi Shamir. Ip = pspace. Journal of the ACM , 39(4), January 1992

    1992

  17. [25]

    On general minimax theorems

    Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics , 8(1), 1958

    1958

  18. [26]

    A quantum polynomial hierarchy and a simple proof of vyalyi's theorem

    Lieuwe Vinkhuijzen. A quantum polynomial hierarchy and a simple proof of vyalyi's theorem. Master's thesis, Leiden Institute of Advanced Computer Science (LIACS), Leiden University, 2018. Master of Computer Science

    2018

  19. [27]

    Valiant and Vijay V

    Leslie G. Valiant and Vijay V. Vazirani. Np is as easy as detecting unique solutions. Theoretical Computer Science , 47(1), 1986

    1986

  20. [28]

    The Theory of Quantum Information

    John Watrous. The Theory of Quantum Information . Cambridge University Press, 2018

    2018

  21. [29]

    Quantum np and a quantum hierarchy

    Tomoyuki Yamakami. Quantum np and a quantum hierarchy. arXiv:quant-ph/0308125 , 2003

    2003 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.