Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2111.02999 · Leibniz international proceedings in informatics

Quantum Search-To-Decision Reductions and the State Synthesis Problem

Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen

Published Nov 4, 2021• 8 citations
arXivHTMLPDF

Abstract

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 $\textit{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 $\mathsf{QMA}$, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a $\mathsf{QMA}$ problem up to inverse polynomial precision by making one query to a $\mathsf{PP}$ decision oracle. We complement this result by showing that $\mathsf{QMA}$-search does $\textit{not}$ reduce to $\mathsf{QMA}$-decision in polynomial-time, relative to a quantum oracle. We also explore the more general $\textit{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.

DOI
10.4230/lipics.ccc.2022.5

Related papers

Finding quantum partial assignments by search-to-decision reductions

Jordi R. Weggemans

In computer science, many search problems are reducible to decision problems, which implies that finding a solution is as hard as deciding whether a solution exists. A quantum analogue of search-to-decision reductions would be to ask whether a quantum algorithm with access to a $\mathsf{QMA}$ oracle can construct $\mathsf{QMA}$ witnesses as quantum states. By a result from Irani, Natarajan, Nirkhe, Rao, and Yuen (CCC '22), it is known that this does not hold relative to a quantum oracle, unlike the cases of $\mathsf{NP}$, $\mathsf{MA}$, and $\mathsf{QCMA}$ where search-to-decision relativizes. We prove that if one is not interested in the quantum witness as a quantum state but only in terms of its partial assignments, i.e. the reduced density matrices, then there exists a classical polynomial-time algorithm with access to a $\mathsf{QMA}$ oracle that outputs approximations of the density matrices of a near-optimal quantum witness, for any desired constant locality and inverse polynomial error. Our construction is based on a circuit-to-Hamiltonian mapping that approximately preserves near-optimal $\mathsf{QMA}$ witnesses and a new $\mathsf{QMA}$-complete problem, Low-energy Density Matrix Verification, which is called by the $\mathsf{QMA}$ oracle to adaptively construct approximately consistent density matrices of a low-energy state.

arXiv:2408.03986•Aug 7, 2024•0 citations

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

quant-pharXiv:2607.26478•Jul 30, 2026•0 citations

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

Unitary complexity in polynomial space

William Kretschmer, Ewin Tang

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that $\mathsf{unitaryPSPACE}$ has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

quant-pharXiv:2610.03705•Oct 5, 2026•0 citations

Efficient Quantum State Synthesis with One Query

Gregory Rosenthal

We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state |ψ〉 there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of |ψ〉. Previous algorithms for this problem either used a linear number of queries and polynomial time, or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime. As corollaries we do the following:

arXiv:2306.01723•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•5 citations

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography

Alex Lombardi, Fermi Ma, John Wright

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

arXiv:2310.08870•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•16 citations
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\textit{de facto}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\mathsf{QMA}QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA\mathsf{QMA}QMA problem up to inverse polynomial precision by making one query to a PP\mathsf{PP}PP decision oracle. We complement this result by showing that QMA\mathsf{QMA}QMA-search does not\textit{not}not reduce to QMA\mathsf{QMA}QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem\textit{state synthesis problem}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)O(n)O(n) queries to a classical oracle to prepare an nnn-qubit state, and asked if the query complexity could be made sublinear.
In computer science, many search problems are reducible to decision problems, which implies that finding a solution is as hard as deciding whether a solution exists. A quantum analogue of search-to-decision reductions would be to ask whether a quantum algorithm with access to a QMA\mathsf{QMA}QMA oracle can construct QMA\mathsf{QMA}QMA witnesses as quantum states. By a result from Irani, Natarajan, Nirkhe, Rao, and Yuen (CCC '22), it is known that this does not hold relative to a quantum oracle, unlike the cases of NP\mathsf{NP}NP, MA\mathsf{MA}MA, and QCMA\mathsf{QCMA}QCMA where search-to-decision relativizes. We prove that if one is not interested in the quantum witness as a quantum state but only in terms of its partial assignments, i.e. the reduced density matrices, then there exists a classical polynomial-time algorithm with access to a QMA\mathsf{QMA}QMA oracle that outputs approximations of the density matrices of a near-optimal quantum witness, for any desired constant locality and inverse polynomial error. Our construction is based on a circuit-to-Hamiltonian mapping that approximately preserves near-optimal QMA\mathsf{QMA}QMA witnesses and a new QMA\mathsf{QMA}QMA-complete problem, Low-energy Density Matrix Verification, which is called by the QMA\mathsf{QMA}QMA oracle to adaptively construct approximately consistent density matrices of a low-energy state.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every nnn-qubit unitary UUU is computable by efficient quantum circuits relative to some classical oracle f=fUf = f_Uf=fU​ depending on UUU. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n)(n)(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩P\lvert x\rangle = \lvert π(x)\rangleP∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1F_2 \cdot H^{\otimes n} \cdot F_1F2​⋅H⊗n⋅F1​. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩\lvert x\rangle\mapsto α_x \lvert x\rangle∣x⟩↦αx​∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(log⁡n)Ω(\log n)Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(log⁡n)Ω(\log n)Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP≠NEXP\mathsf{BPP} \neq \mathsf{NEXP}BPP=NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP\mathsf{NEXP}NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE would imply breakthrough classical lower bounds such as NC≠NP\mathsf{NC} \neq \mathsf{NP}NC=NP. Along the way, we propose new definitions for the unitary complexity classes unitaryP\mathsf{unitaryP}unitaryP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.