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

Topological obstructions to implementing controlled unknown unitaries

Zuzana Gavorová, Matan Seidel, Yonathan Touati

Published Nov 19, 2020• 13 citations
OpenAlex

Abstract

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.

Related papers

Topological obstructions to quantum computation with unitary oracles

Zuzana Gavorová, Matan Seidel, Yonathan Touati

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

arXiv:2011.10031•Physical Review A•Mar 28, 2024•29 citations

Quantum circuits cannot control unknown operations

Mateus Araújo, Adrien Feix, Fabio Costa +1 more

One of the essential building blocks of classical computer programs is the ' if ' clause, which executes a subroutine depending on the value of a control variable. Similarly, several quantum algorithms rely on applying a unitary operation conditioned on the state of a control system. Here we show that this control cannot be performed by a quantum circuit if the unitary is completely unknown. The task remains impossible even if we allow the control to be done modulo a global phase. However, this no-go theorem does not prevent implementing quantum control of unknown unitaries in practice, as any physical implementation of an unknown unitary provides additional information that makes the control possible. We then argue that one should extend the quantum circuit formalism to capture this possibility in a straightforward way. This is done by allowing unknown unitaries to be applied to subspaces and not only to subsystems.

arXiv:1309.7976•New Journal of Physics•Sep 22, 2014•143 citations

Quantum Computing with black-box Subroutines

Jayne E. Thompson, Mile Gu, Kavan Kishore Modi +1 more

Modern programming relies on our ability to treat preprogrammed functions as black boxes - we can invoke them as subroutines without knowing their physical implementation. Here we show it is generally impossible to execute an unknown quantum subroutine. This, as a special case, forbids applying black-box subroutines conditioned on an ancillary qubit. We explore how this limits many quantum algorithms - forcing their circuit implementation to be individually tailored to specific inputs and inducing failure if these inputs are not known in advance. We present a method to avoid this situation for certain computational problems. We apply this method to enhance existing quantum factoring algorithms; reducing their complexity, and the extent to which they need to be tailored to factor specific numbers. Thus, we highlight a natural property of classical information that fails in the advent of quantum logic; and simultaneously demonstrate how to mitigate its effects in practical situations.

arXiv:1310.2927•Oct 10, 2013•39 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

Possible Implementations of Oracles in Quantum Algorithms

Jiahao Zhao

Abstract Quantum computing is an inspiring technic on solving complicate problems, which shows the superiority over the classical computing. Contemporarily, the quantum-based algorithms were invented in many purposes on solving those problems. The thing is some of the algorithms were composed with oracles, which can be treated as a black box. It can be worked out/analyzed in theoretical mathematical expressions, but it can never fall in the ground without those actual implementations. Therefore, this paper will illustrate the idea and possible implementations on some quantum algorithm. Among various algorithms, this research will choose those relatively famous quantum algorithms, i.e., Deutsch-Jozsa Algorithm, Shor’s Algorithm, and Grover’s Algorithm. Different algorithms have the different intrinsic logics, which means there is no general description for all solution in this problem, but all of those can achieve the goal according to the same framework. Since those oracles are black boxes that can only be analyzed by its behavior with different cases, and then based on the behaviors and cases, and in IBM quantum platform, one can fill out the oracle by manipulate with different quantum operators. Lastly, the figures of some the possible implementation of those oracles with the three quantum algorithms will be shown in the IBM quantum platform, as well as the histograms of probability distributions that can justify the correctness of the implementations. These results shed light on guiding further exploration of the design and analysis on quantum algorithms.

Journal of Physics Conference Series•Dec 1, 2022•1 citation

Unitarization Through Approximate Basis

Joshua Alan Cook

We introduce the problem of unitarization. Unitarization is the problem of taking $k$ input quantum circuits that produce orthogonal states from the all $0$ state, and create an output circuit implementing a unitary with its first $k$ columns as those states. That is, the output circuit takes the $k$th computational basis state to the state prepared by the $k$th input circuit. We allow the output circuit to use ancilla qubits initialized to $0$. But ancilla qubits must always be returned to $0$ for any input. The input circuits may use ancilla qubits, but we are only guaranteed the they return ancilla qubits to $0$ on the all $0$ input. The unitarization problem seems hard if the output states are neither orthogonal to or in the span of the computational basis states that need to map to them. In this work, we approximately solve this problem in the case where input circuits are given as black box oracles by probably finding an approximate basis for our states. This method may be more interesting than the application. This technique is a sort of quantum analogue of Gram-Schmidt orthogonalization for quantum states. Specifically, we find an approximate basis in polynomial time for the following parameters. Take any natural $n$, $k = O\left(\frac{\ln(n)}{\ln(\ln(n))}\right)$, and $ε= 2^{-O(\sqrt{\ln(n)})}$. Take any $k$ input quantum states, $(|ψ_i \rangle)_{i\in [k]}$, on polynomial in $n$ qubits prepared by quantum oracles, $(V_i)_{i \in [k]}$ (that we can control call and control invert). Then there is a quantum circuit with polynomial size in $n$ with access to the oracles $(V_i)_{i \in [k]}$ that with at least $1 - ε$ probability, computes at most $k$ circuits with size polynomial in $n$ and oracle access to $(V_i)_{i \in [k]}$ that $ε$ approximately computes an $ε$ approximate orthonormal basis for $(|ψ_i \rangle)_{i\in [k]}$.

arXiv:2104.00785•Apr 1, 2021•0 citations
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.
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
One of the essential building blocks of classical computer programs is the ' if ' clause, which executes a subroutine depending on the value of a control variable. Similarly, several quantum algorithms rely on applying a unitary operation conditioned on the state of a control system. Here we show that this control cannot be performed by a quantum circuit if the unitary is completely unknown. The task remains impossible even if we allow the control to be done modulo a global phase. However, this no-go theorem does not prevent implementing quantum control of unknown unitaries in practice, as any physical implementation of an unknown unitary provides additional information that makes the control possible. We then argue that one should extend the quantum circuit formalism to capture this possibility in a straightforward way. This is done by allowing unknown unitaries to be applied to subspaces and not only to subsystems.
Modern programming relies on our ability to treat preprogrammed functions as black boxes - we can invoke them as subroutines without knowing their physical implementation. Here we show it is generally impossible to execute an unknown quantum subroutine. This, as a special case, forbids applying black-box subroutines conditioned on an ancillary qubit. We explore how this limits many quantum algorithms - forcing their circuit implementation to be individually tailored to specific inputs and inducing failure if these inputs are not known in advance. We present a method to avoid this situation for certain computational problems. We apply this method to enhance existing quantum factoring algorithms; reducing their complexity, and the extent to which they need to be tailored to factor specific numbers. Thus, we highlight a natural property of classical information that fails in the advent of quantum logic; and simultaneously demonstrate how to mitigate its effects in practical situations.
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.
Abstract Quantum computing is an inspiring technic on solving complicate problems, which shows the superiority over the classical computing. Contemporarily, the quantum-based algorithms were invented in many purposes on solving those problems. The thing is some of the algorithms were composed with oracles, which can be treated as a black box. It can be worked out/analyzed in theoretical mathematical expressions, but it can never fall in the ground without those actual implementations. Therefore, this paper will illustrate the idea and possible implementations on some quantum algorithm. Among various algorithms, this research will choose those relatively famous quantum algorithms, i.e., Deutsch-Jozsa Algorithm, Shor’s Algorithm, and Grover’s Algorithm. Different algorithms have the different intrinsic logics, which means there is no general description for all solution in this problem, but all of those can achieve the goal according to the same framework. Since those oracles are black boxes that can only be analyzed by its behavior with different cases, and then based on the behaviors and cases, and in IBM quantum platform, one can fill out the oracle by manipulate with different quantum operators. Lastly, the figures of some the possible implementation of those oracles with the three quantum algorithms will be shown in the IBM quantum platform, as well as the histograms of probability distributions that can justify the correctness of the implementations. These results shed light on guiding further exploration of the design and analysis on quantum algorithms.
We introduce the problem of unitarization. Unitarization is the problem of taking kkk input quantum circuits that produce orthogonal states from the all 000 state, and create an output circuit implementing a unitary with its first kkk columns as those states. That is, the output circuit takes the kkkth computational basis state to the state prepared by the kkkth input circuit. We allow the output circuit to use ancilla qubits initialized to 000. But ancilla qubits must always be returned to 000 for any input. The input circuits may use ancilla qubits, but we are only guaranteed the they return ancilla qubits to 000 on the all 000 input. The unitarization problem seems hard if the output states are neither orthogonal to or in the span of the computational basis states that need to map to them. In this work, we approximately solve this problem in the case where input circuits are given as black box oracles by probably finding an approximate basis for our states. This method may be more interesting than the application. This technique is a sort of quantum analogue of Gram-Schmidt orthogonalization for quantum states. Specifically, we find an approximate basis in polynomial time for the following parameters. Take any natural nnn, k=O(ln⁡(n)ln⁡(ln⁡(n)))k = O\left(\frac{\ln(n)}{\ln(\ln(n))}\right)k=O(ln(ln(n))ln(n)​), and ε=2−O(ln⁡(n))ε= 2^{-O(\sqrt{\ln(n)})}ε=2−O(ln(n)​). Take any kkk input quantum states, (∣ψi⟩)i∈[k](|ψ_i \rangle)_{i\in [k]}(∣ψi​⟩)i∈[k]​, on polynomial in nnn qubits prepared by quantum oracles, (Vi)i∈[k](V_i)_{i \in [k]}(Vi​)i∈[k]​ (that we can control call and control invert). Then there is a quantum circuit with polynomial size in nnn with access to the oracles (Vi)i∈[k](V_i)_{i \in [k]}(Vi​)i∈[k]​ that with at least 1−ε1 - ε1−ε probability, computes at most kkk circuits with size polynomial in nnn and oracle access to (Vi)i∈[k](V_i)_{i \in [k]}(Vi​)i∈[k]​ that εεε approximately computes an εεε approximate orthonormal basis for (∣ψi⟩)i∈[k](|ψ_i \rangle)_{i\in [k]}(∣ψi​⟩)i∈[k]​.