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:2607.26478

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

quant-phcs.CCcs.CRSubmitted Jul 29, 2026• Announced Jul 30, 2026• 3 citations
arXivHTMLPDF

Abstract

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.

Related papers

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•40 citations

Random-Oracle Unitary Synthesis is Impossible

Andrew Huang, Akshar Ramkumar, John Wright

A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case'' unitary synthesis problem, which asks whether it is possible to efficiently implement a Haar random unitary given access to a random Boolean function. We then demonstrate a superpolynomial query lower bound, establishing that unitary synthesis in this model is impossible. Along with our main result, we settle in the negative a question Brakerski and Yuen pose, of whether scalable pseudorandom unitaries (PRUs) can be implemented in the ROM-PRU model. In particular, we show that in the ROM-PRU model, no $Ω(N^{1+γ})$ unitary design on $n$ qubits, where $N=2^n$, can be efficiently achieved for any $γ> 0$. On the other hand, we construct an $O(N)$-design in $\text{poly}(n)$ queries in the same model, surpassing the previously best known results which constructed $O(\sqrt{N})$-designs.

quant-pharXiv:2610.06700•Oct 6, 2026•1 citation

unitaryQIP = unitaryPSPACE

Entong He, Fengning Ou, Mingnan Zhao

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: $\mathsf{unitaryQIP}$ and $\mathsf{unitaryPSPACE}$ for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$ and thereby establish a unitary-complexity analogue of $\mathsf{QIP} = \mathsf{PSPACE}$ (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and $\mathsf{stateQIP}=\mathsf{statePSPACE}$ (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove $\mathsf{unitaryQIP} \subseteq \mathsf{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 $\mathsf{unitaryPSPACE}$ families can be synthesized in polynomial time with a $\mathsf{PSPACE}$ oracle. We then implement the oracle queries using auxiliary states prepared via the $\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}$ protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for $\mathsf{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 $\mathsf{EFI}$ pairs.

quant-pharXiv:2611.02819•Nov 3, 2026•0 citations

A 1.5-Query Lower Bound for the Unitary Synthesis Problem

Eric Huang

We prove a new lower bound for the unitary synthesis problem in the so-called 1.5-query setting. Our analysis establishes that any attempt to implement arbitrary n-qubit unitaries via limited oracle access requires resources that exceed the fractional query threshold. This result extends the one-query lower bound of Lombardi, Ma, and Wright (2023) to the fractional query regime, and introduces a conservative and chaining-based approach to handle intermediate query complexities. As a consequence, we derive cryptographic implications, showing that pseudorandom quantum states remain secure against adversaries restricted to 1.5 queries. Our work provides both conceptual clarification of fractional-query complexity and practical insights into the design of quantum cryptographic protocols.

arXiv:2508.13215•Aug 17, 2025•1 citation

State Synthesis with an NP oracle

Aniruddha Sen

In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming one can directly query entries of the state vector corresponding to $|ψ\rangle$. The previous best upper bound on the complexity class required by an oracle for this task was $\mathsf{PP}$. I provide evidence that $\mathsf{NP}$ is the best possible upper bound by showing that any quantum algorithm using a $\mathsf{P}$ oracle, or even a $\mathsf{P/poly}$ oracle, requires exponentially many queries. I also discuss some implications of this result for the $\mathsf{QMA}$ search-to-decision problem and unitary synthesis.

quant-pharXiv:2611.02370•Nov 3, 2026•0 citations

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

quant-pharXiv:2610.02101•Oct 2, 2026•1 citation
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.
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.
A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case'' unitary synthesis problem, which asks whether it is possible to efficiently implement a Haar random unitary given access to a random Boolean function. We then demonstrate a superpolynomial query lower bound, establishing that unitary synthesis in this model is impossible. Along with our main result, we settle in the negative a question Brakerski and Yuen pose, of whether scalable pseudorandom unitaries (PRUs) can be implemented in the ROM-PRU model. In particular, we show that in the ROM-PRU model, no Ω(N1+γ)Ω(N^{1+γ})Ω(N1+γ) unitary design on nnn qubits, where N=2nN=2^nN=2n, can be efficiently achieved for any γ>0γ> 0γ>0. On the other hand, we construct an O(N)O(N)O(N)-design in poly(n)\text{poly}(n)poly(n) queries in the same model, surpassing the previously best known results which constructed O(N)O(\sqrt{N})O(N​)-designs.
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\mathsf{unitaryQIP}unitaryQIP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality unitaryQIP=unitaryPSPACE\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}unitaryQIP=unitaryPSPACE and thereby establish a unitary-complexity analogue of QIP=PSPACE\mathsf{QIP} = \mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and stateQIP=statePSPACE\mathsf{stateQIP}=\mathsf{statePSPACE}stateQIP=statePSPACE (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove unitaryQIP⊆unitaryPSPACE\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}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\mathsf{unitaryPSPACE}unitaryPSPACE families can be synthesized in polynomial time with a PSPACE\mathsf{PSPACE}PSPACE oracle. We then implement the oracle queries using auxiliary states prepared via the statePSPACE⊆stateQIP\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}statePSPACE⊆stateQIP protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for unitaryPSPACE\mathsf{unitaryPSPACE}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\mathsf{EFI}EFI pairs.
We prove a new lower bound for the unitary synthesis problem in the so-called 1.5-query setting. Our analysis establishes that any attempt to implement arbitrary n-qubit unitaries via limited oracle access requires resources that exceed the fractional query threshold. This result extends the one-query lower bound of Lombardi, Ma, and Wright (2023) to the fractional query regime, and introduces a conservative and chaining-based approach to handle intermediate query complexities. As a consequence, we derive cryptographic implications, showing that pseudorandom quantum states remain secure against adversaries restricted to 1.5 queries. Our work provides both conceptual clarification of fractional-query complexity and practical insights into the design of quantum cryptographic protocols.
In this note, I describe a quantum algorithm that prepares an arbitrary state ∣ψ⟩|ψ\rangle∣ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP\mathsf{NP}NP oracle, assuming one can directly query entries of the state vector corresponding to ∣ψ⟩|ψ\rangle∣ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP\mathsf{PP}PP. I provide evidence that NP\mathsf{NP}NP is the best possible upper bound by showing that any quantum algorithm using a P\mathsf{P}P oracle, or even a P/poly\mathsf{P/poly}P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA\mathsf{QMA}QMA search-to-decision problem and unitary synthesis.
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a TTT-query adversary with SSS qubits of non-uniform advice can recover a random key kkk from the nnn-qubit binary phase state ∣ψk⟩∝∑xR(k,x)∣x⟩|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle∣ψk​⟩∝∑x​R(k,x)∣x⟩ with probability at most O(T2+STN)O(\frac{T^2 + \sqrt{ST}}{N})O(NT2+ST​​) for N=2nN=2^nN=2n. In contrast, the best known bound for post-quantum one-way functions is O(T2+STN)O(\frac{T^2 + ST}{N})O(NT2+ST​), with a trivial attack at S=NS = NS=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: nnn qubits of communication suffice for security against preprocessing attacks with space up to N2N^2N2 rather than NNN. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(T2N+STN)O(\frac{T^2}N + \sqrt{\frac{ST}N})O(NT2​+NST​​). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(SN)O(\frac{\sqrt{S}}N)O(NS​​) bound for the pseudorandomness of random binary phase states against space SSS distinguishers.