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
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 d-dimensional unitary 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 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 ϕ(U), even if allowed any finite number of calls to U and U†, and even if required to only approximate the desired operator 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) with a nonzero probability for each 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) 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∈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 create a superposition αeiϕ(∣u⟩,∣v⟩)∣u⟩+β∣v⟩ for some real function ϕ. 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 - 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.
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.
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=fU 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∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅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⟩, 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.
Quantum computers have shown great promise as a resource providing exponential speedup over classical computers for certain problems.Akin to their classical counterparts, quantum computers will be prone to errors.There are two major sources of errors.First, the most formidable source of error is decoherence.To perform quantum computation, quantum information must be stored, processed and read out while protecting it from the debilitating effects of decoherence.Second, even if the system is protected from decoherence, it is almost certain that all the operations performed on the quantum information during its processing will be imperfect.These errors will accumulate over the duration of the computation, eventually causing failure.Thus, for a quantum computing scheme to be feasible, it needs to be fault-tolerant.What this means is that the quantum computer can still perform its task effectively while its components are imperfect.A major breakthrough in this field is the threshold theorem, which asserts that ideal quantum circuits can be simulated efficiently by noisy ones provided the error rates of individual gates are below a certain threshold [1,2,3].Topological quantum computing is an approach to fault-tolerant quantum computation, where the protection from errors occurs not from active intervention, but at a hardware level.The advantage of this approach is that it is robust to localized imperfections.First envisioned by Alexei Kitaev [4], this scheme makes use of a non-abelian exchange statistics of elementary excitations of some two-dimensional quantum many-body system.These excitations form the degenerate ground-space of this topologically ordered system, and all other states are separated from this space by a finite excitation gap.In order to perform computation in this scheme, one needs to create pairs of these non-abelian excitations (called non-abelian anyons) from vacuum, separating them spatially, transporting them around each other to implement the logical gates and finally, fusing them together for measurements.In order for this scheme to be viable, there are two conditions that must be fulfilled.First, there could be errors due to quantum tunneling between the non-abelian anyons.These processes can take place even at zero temperature.But, the amplitude of these processes are exponentially suppressed with the spatial separation of these particles and goes as e -L/l 0 , where L is the spatial separation and l 0 is some characteristic length scale of topological ordering of the system.Thus, to prevent such tunneling during quantum information processing and storage, L has to be much larger than l 0 .Second, at finite temperature, undesired thermally excited quasiparticles can lead to errors.The generation rate of these particles are exponentially suppressed by a Boltzmann factor e -∆/T , where ∆ is the excitation energy and T is the temperature.Therefore, the temperature must be low enough so that there are sufficiently low number of these undesired excitations.There are several physical systems where these excitations could, in principle, be found, manipulated and measured.Non-abelian anyons were proposed as elementary excitations of the ν = 5/2 state in the fractional quantum hall effect [5].The braiding statistics of these particles and their possible use in quantum computing has been investigated thoroughly.For more information on this topic, the reader is invited to consult [6,7].In a pathbreaking work [8], it was proposed that the non-abelian statistics of the excitations of the ν = 5/2 state are shared by the Majorana excitations of a 2D spinless p + ip superconductor.Since then, there have been other theoretical models [9,10] which also support these non-abelian excitations.Moreover, several experimental realizations of these Majorana excitations in solid state systems have also been proposed (for a comprehensive review, see [11]).In this lecture note, we will focus on implementation of topological quantum computation with
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.