This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparing quantum states) and traditional decision complexity classes. We especially investigate the role of the \emph{synthesis error parameter}, which characterizes the quality of the synthesis in quantum state synthesis complexity classes.We first show that in the high synthesis error regime, collapse of synthesis classes implies collapse of the equivalent decision classes. For more reasonable synthesis error, we then show a similar relationships for $\BQP$ and $\QCMA$. Finally, we show that for quantum state synthesis classes it is in general impossible to improve the quality of the synthesis: unlike the completeness and soundness parameters (which can be improved via repetition), the synthesis error cannot be reduced, even with arbitrary computational power.
This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparing quantum states) and traditional decision complexity classes. We especially investigate the role of the \emph{synthesis error parameter}, which characterizes the quality of the synthesis in quantum state synthesis complexity classes.We first show that in the high synthesis error regime, collapse of synthesis classes implies collapse of the equivalent decision classes. For more reasonable synthesis error, we then show a similar relationships for \BQP and \QCMA. Finally, we show that for quantum state synthesis classes it is in general impossible to improve the quality of the synthesis: unlike the completeness and soundness parameters (which can be improved via repetition), the synthesis error cannot be reduced, even with arbitrary computational power.
This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparing quantum states) and traditional decision complexity classes. We especially investigate the role of the synthesis error parameter, which characterizes the quality of the synthesis in quantum state synthesis complexity classes. We first show that in the high synthesis error regime, collapse of synthesis classes implies collapse of the equivalent decision classes. For more reasonable synthesis error, we then show a similar relationships for BQP and QCMA. Finally, we show that for quantum state synthesis classes it is in general impossible to improve the quality of the synthesis: unlike the completeness and soundness parameters (which can be improved via repetition), the synthesis error cannot be reduced, even with arbitrary computational power.
Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: unitaryQIP and unitaryPSPACE for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality unitaryQIP=unitaryPSPACE and thereby establish a unitary-complexity analogue of QIP=PSPACE (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and stateQIP=statePSPACE (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023).
To prove unitaryQIP⊆unitaryPSPACE, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that unitaryPSPACE families can be synthesized in polynomial time with a PSPACE oracle. We then implement the oracle queries using auxiliary states prepared via the statePSPACE⊆stateQIP protocol (Rosenthal and Yuen, ITCS 2022).
Beyond the equality, we show that our protocol for unitaryPSPACE can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of EFI pairs.
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA problem up to inverse polynomial precision by making one query to a PP decision oracle. We complement this result by showing that QMA-search does not reduce to QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes O(n) queries to a classical oracle to prepare an n-qubit state, and asked if the query complexity could be made sublinear.
In this note, I describe a quantum algorithm that prepares an arbitrary state ∣ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP oracle, assuming one can directly query entries of the state vector corresponding to ∣ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP. I provide evidence that NP is the best possible upper bound by showing that any quantum algorithm using a P oracle, or even a P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA search-to-decision problem and unitary synthesis.
Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class NP , referred to as stateQMA , which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022) \cite{RY22}, which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits ( stateBQP ) and space-uniform polynomial-space quantum circuits ( statePSPACE ). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA . Additionally, we demonstrate that stateQCMA achieves perfect completeness.
Parity ∈/ QAC0 ⟺ QAC0 is Fourier-Concentrated
A major open problem in understanding shallow quantum circuits (QAC0) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC0: any QAC0 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0. Thus, proving a quantum analog of the seminal LMN theorem for AC0 is necessary to bound the quantum circuit complexity of PARITY.
In the other direction, LMN does not fully capture the limitations of AC0. For example, despite MAJORITY having 99% of its weight on low-degree Fourier coefficients, no AC0 circuit can non-trivially correlate with it. In contrast, we provide a QAC0 circuit that achieves (1−o(1)) correlation with MAJORITY, establishing the first average-case decision separation between AC0 and QAC0. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC0.
PARITY is also known to be equivalent in QAC0 to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY ∈ QAC0.