Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)\geq n^4$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length m(n)≥n4 and every error bound ε(n) that stays below 1/2 by at least an inverse polynomial, there is a positive function δ with δ(n)=O(min{(logm/m)1/4,logm/m/(1/2−ε(n))}) such that BQPε/qm⊊BQPε+δ/qm; for constant ε the gap is O(logm/m). Here, BQPε/qm is the class of languages recognizable with error at most ε(n) by a polynomial-time quantum algorithm with an m(n)-qubit advice state that only depends on the input length n. We show this by proving a stronger separation Pε+δ/rm⊂BQPε/qm, where Pε/rm is the class of languages recognizable with error at most ε(n) by a deterministic polynomial-time algorithm with an m(n)-bit advice string sampled from a distribution that depends only on n.
The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by k separate polynomial-time verifiers, for arbitrary polynomial k. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.
It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{0,1}n that maximizes the acceptance probability of C up to a δ additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)<δ<1. For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant. On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
We prove the following surprising result: given any quantum state ρ on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate ρ on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly⊆QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly⊆PP/poly. Indeed, we can exactly characterize quantum advice as equivalent in power to untrusted quantum advice combined with trusted classical advice. Proving our main result requires combining a large number of previous tools---including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on “QMA+ super-verifiers''---and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set S of Boolean functions on n variables, any function f∈S can be expressed as the pointwise majority of m=O(n) functions f1,…,fm∈S, such that each fi is the unique function in S compatible with O(log∣S∣) input/output constraints.
Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for deterministic and randomized computation (FP, FBPP) and advice (/poly, /rpoly). Our first result is that FBQP/qpoly ≠ FBQP/poly, unconditionally, with no oracle - a striking contrast with what we know about the analogous decision classes. The proof repurposes the separation between quantum and classical one-way communication complexities due to Bar-Yossef, Jayram, and Kerenidis. We discuss how this separation raises the prospect of near-term experiments to demonstrate "quantum information supremacy," a form of quantum supremacy that would not depend on unproved complexity assumptions. Our second result is that FBPP ̸ ⊂ FP/poly - that is, Adleman’s Theorem fails for relational problems - unless PSPACE ⊂ NP/poly. Our proof uses IP = PSPACE and time-bounded Kolmogorov complexity. On the other hand, we show that proving FBPP ̸ ⊂ FP/poly will be hard, as it implies a superpolynomial circuit lower bound for PromiseBPEXP. We prove the following further results: - Unconditionally, FP ≠ FBPP and FP/poly ≠ FBPP/poly (even when these classes are carefully defined). - FBPP/poly = FBPP/rpoly (and likewise for FBQP). For sampling problems, by contrast, SampBPP/poly ≠ SampBPP/rpoly (and likewise for SampBQP).
It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{0,1}n that maximizes the acceptance probability of C up to a δ additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)<δ<1. For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant.
On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.