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:2011.10031 · Physical Review A

Topological obstructions to quantum computation with unitary oracles

Zuzana Gavorová, Matan Seidel, Yonathan Touati

Published Mar 28, 2024• 29 citations
arXivHTMLPDF

Abstract

Algorithms with unitary oracles can be nested, which makes them extremely versatile. An example is the phase estimation algorithm used in many candidate algorithms for quantum speedup. The search for new quantum algorithms benefits from understanding their limitations: Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. An example with a unitary oracle U is the if clause, the task to implement controlled U (up to the phase on U ). In classical computation the conditional statement is easy and essential. In quantum circuits the if clause was shown impossible from one query to U . Is it possible from polynomially many queries? Here we unify algorithms with a unitary oracle and develop a topological method to prove their limitations: No number of queries to U and U† lets quantum circuits implement the if clause, even if admitting approximations, postselection, and relaxed causality. We also show limitations of process tomography, oracle neutralization, and UdimU, UT , and U† algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements. Published by the American Physical Society 2024

DOI
10.1103/physreva.109.032625

Related papers

Topological obstructions to implementing controlled unknown unitaries

Zuzana Gavorová, Matan Seidel, Yonathan Touati

Is a quantum algorithm capable of implementing an if-clause? Given a black-box subroutine, a $d$-dimensional unitary $U\in U(d)$, a quantum if-clause would correspond to applying it to an input qudit if and only if the value of a control qubit is $1$. It was previously shown by Thompson et al. and Araujo et al. that implementations using single access to the oracle $U$ are impossible. Our main result is a strong generalization of this impossibility result: we prove that there is no unitary oracle algorithm implementing $control_\phi(U)=\left|0\right>\!\!\left \!\!\left<1\right|\otimes U$, for some $U$-dependent phase $\phi(U)$, even if allowed any finite number of calls to $U$ and $U^\dagger$, and even if required to only approximate the desired operator $control_\phi(U)$. Even further, there is no such \emph{postselection} oracle algorithm, i.e. a unitary oracle algorithm followed by a binary success/fail measurement, that reports success and implements $control_\phi(U)$ with a nonzero probability for each $U\in U(d)$. Our proof relies on topological arguments which can be viewed as a modification of the Borsuk-Ulam theorem. Combining the topological arguments with the algorithm of Dong et al. in fact leads to an interesting dichotomy: implementing $control_\phi(U^m)$ in our model is possible if and only if the integer $m$ is a multiple of the oracle's dimension $d$. Our impossibility no longer holds if the model is relaxed, either by dropping the worst-case requirement that the algorithm works for all $U\in U(d)$, or, remarkably, by allowing measurements more general than a binary postselection measurement. We observe that for both relaxations, inefficient algorithms exist, and it remains open whether efficient ones do.

•Nov 19, 2020•13 citations

Topologically-driven impossibility of superposing unknown states.

Zuzana Gavorová

Our understanding of quantum mechanics broadens by discovering tasks that are easy classically but their quantum versions are impossible, such as cloning. Another such task is the superposition task: Given two input states $\left|u\right>,\left|v\right>\in\mathcal{H}$ create a superposition $\alpha e^{i\phi(\left|u\right>,\left|v\right>)} \left|u\right>+\beta\left|v\right>$ for some real function $\phi$. This is the quantum version of the classical adder. Oszmaniec, Grudka, Horodecki and W\'ojcik [1] showed that a quantum circuit acting on a single pair of input states cannot output an exact superposition of them. Here we prove that a quantum circuit cannot approximate a superposition for every pair of states in $\mathcal{H}$ - even if it accesses any number of copies of the input states. Our proof follows the [2]: Any quantum circuit defines a continuous function on the input states. Using new topological arguments we prove that no continuous function can have the desired output. Compared to methods that view quantum circuits as linear [3-5] or polynomial [6] functions, the topological method excludes any number of input-state copies. We give some intuition of why the method is applicable to the superposition task. We consider the following protocol: given a large number of copies of the two input states, use state tomography to obtain a classical description of each, then prepare their superposition from scratch. Comparing our impossibility to this tomography protocol, we find a separation between two types of measurement.

•Nov 3, 2021•0 citations

Opening the Black Box inside Grover’s Algorithm

Edwin Miles Stoudenmire, Xavier Waintal

Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024

arXiv:2303.11317•Physical Review X•Nov 1, 2024•56 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•3 citations

Quantum query complexity of Boolean functions under indefinite causal order

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau

The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher-order quantum computations. To this end, we generalize the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps. Published by the American Physical Society 2024

arXiv:2307.10285•Physical Review Research•Jul 26, 2024•12 citations

How Much Structure Is Needed for Huge Quantum Speedups?

Scott Aaronson

I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit model, which is what we ultimately care about in practice but where our knowledge is radically incomplete, and the so-called oracle or black-box or query complexity model, where we've managed to achieve a much more thorough understanding that then informs our conjectures about the circuit model. I discuss the strengths and weaknesses of switching attention to sampling tasks, as was done in the recent quantum supremacy experiments. I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).

arXiv:2209.06930•Sep 14, 2022•63 citations
Algorithms with unitary oracles can be nested, which makes them extremely versatile. An example is the phase estimation algorithm used in many candidate algorithms for quantum speedup. The search for new quantum algorithms benefits from understanding their limitations: Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. An example with a unitary oracle U is the if clause, the task to implement controlled U (up to the phase on U ). In classical computation the conditional statement is easy and essential. In quantum circuits the if clause was shown impossible from one query to U . Is it possible from polynomially many queries? Here we unify algorithms with a unitary oracle and develop a topological method to prove their limitations: No number of queries to U and U† lets quantum circuits implement the if clause, even if admitting approximations, postselection, and relaxed causality. We also show limitations of process tomography, oracle neutralization, and UdimU, UT , and U† algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements. Published by the American Physical Society 2024
Is a quantum algorithm capable of implementing an if-clause? Given a black-box subroutine, a ddd-dimensional unitary U∈U(d)U\in U(d)U∈U(d), a quantum if-clause would correspond to applying it to an input qudit if and only if the value of a control qubit is 111. It was previously shown by Thompson et al. and Araujo et al. that implementations using single access to the oracle UUU are impossible. Our main result is a strong generalization of this impossibility result: we prove that there is no unitary oracle algorithm implementing $control_\phi(U)=\left|0\right>\!\!\left \!\!\left<1\right|\otimes U$, for some UUU-dependent phase ϕ(U)\phi(U)ϕ(U), even if allowed any finite number of calls to UUU and U†U^\daggerU†, and even if required to only approximate the desired operator controlϕ(U)control_\phi(U)controlϕ​(U). Even further, there is no such \emph{postselection} oracle algorithm, i.e. a unitary oracle algorithm followed by a binary success/fail measurement, that reports success and implements controlϕ(U)control_\phi(U)controlϕ​(U) with a nonzero probability for each U∈U(d)U\in U(d)U∈U(d). Our proof relies on topological arguments which can be viewed as a modification of the Borsuk-Ulam theorem. Combining the topological arguments with the algorithm of Dong et al. in fact leads to an interesting dichotomy: implementing controlϕ(Um)control_\phi(U^m)controlϕ​(Um) in our model is possible if and only if the integer mmm is a multiple of the oracle's dimension ddd. Our impossibility no longer holds if the model is relaxed, either by dropping the worst-case requirement that the algorithm works for all U∈U(d)U\in U(d)U∈U(d), or, remarkably, by allowing measurements more general than a binary postselection measurement. We observe that for both relaxations, inefficient algorithms exist, and it remains open whether efficient ones do.
Our understanding of quantum mechanics broadens by discovering tasks that are easy classically but their quantum versions are impossible, such as cloning. Another such task is the superposition task: Given two input states ∣u>,∣v>∈H\left|u\right>,\left|v\right>\in\mathcal{H}∣u⟩,∣v⟩∈H create a superposition αeiϕ(∣u>,∣v>)∣u>+β∣v>\alpha e^{i\phi(\left|u\right>,\left|v\right>)} \left|u\right>+\beta\left|v\right>αeiϕ(∣u⟩,∣v⟩)∣u⟩+β∣v⟩ for some real function ϕ\phiϕ. This is the quantum version of the classical adder. Oszmaniec, Grudka, Horodecki and W\'ojcik [1] showed that a quantum circuit acting on a single pair of input states cannot output an exact superposition of them. Here we prove that a quantum circuit cannot approximate a superposition for every pair of states in H\mathcal{H}H - even if it accesses any number of copies of the input states. Our proof follows the [2]: Any quantum circuit defines a continuous function on the input states. Using new topological arguments we prove that no continuous function can have the desired output. Compared to methods that view quantum circuits as linear [3-5] or polynomial [6] functions, the topological method excludes any number of input-state copies. We give some intuition of why the method is applicable to the superposition task. We consider the following protocol: given a large number of copies of the two input states, use state tomography to obtain a classical description of each, then prepare their superposition from scratch. Comparing our impossibility to this tomography protocol, we find a separation between two types of measurement.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024
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 standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher-order quantum computations. To this end, we generalize the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps. Published by the American Physical Society 2024
I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit model, which is what we ultimately care about in practice but where our knowledge is radically incomplete, and the so-called oracle or black-box or query complexity model, where we've managed to achieve a much more thorough understanding that then informs our conjectures about the circuit model. I discuss the strengths and weaknesses of switching attention to sampling tasks, as was done in the recent quantum supremacy experiments. I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).