To better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity N of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and N = 1 , and the matching impossibility of any smaller approximation error for any N . Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open.
To better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity N of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and N = 1 , and the matching impossibility of any smaller approximation error for any N . Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open.
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.
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
The superposition principle is fundamental to quantum theory. Yet a recent no-go theorem has proved that quantum theory forbids superposition of unknown quantum states, even with nonzero probability. The implications of this result, however, remain poorly understood so far. In this Rapid Communication we show that the existence of a protocol that superposes two unknown pure states with nonzero probability (allowed to vary over input states) leads to the violation of other no-go theorems. In particular, such a protocol can be used to perform certain state discrimination and cloning tasks that are forbidden not only in quantum theory but in no-signaling theories as well.
Quantum state tomography (QST), the task of estimating an unknown quantum state given measurement outcomes, is essential to building reliable quantum computing devices. Whereas computing the maximum-likelihood (ML) estimate corresponds to solving a finite-sum convex optimization problem, the objective function is not smooth nor Lipschitz, so most existing convex optimization methods lack sample complexity guarantees; moreover, both the sample size and dimension grow exponentially with the number of qubits in a QST experiment, so a desired algorithm should be highly scalable with respect to the dimension and sample size, just like stochastic gradient descent. In this paper, we propose a stochastic first-order algorithm that computes an ε-approximate ML estimate in O((DlogD)/ε2) iterations with O(D3) per-iteration time complexity, where D denotes the dimension of the unknown quantum state and ε denotes the optimization error. Our algorithm is an extension of Soft-Bayes to the quantum setup.
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting optimal constant factors in the leading terms in a number of different models. In the randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. 2) Using this we obtain a (log(n/ε2)+4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε3)+O(1) upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive loglog(1/ε)+O(1). In the quantum model, 1) we exhibit a one-way protocol of cost log(n/ε)+4, that uses only pure states and computes the n-bit Equality function to error ε. This bound was implicitly already shown by Nayak [PhD thesis'99]. 2) We show that any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε)−loglog(1/ε)−O(1) qubits. 3) We exhibit a one-way protocol of cost log(n/ε)+3, that uses mixed states and computes the n-bit Equality function to error ε. This is also tight up to an additive loglog(1/ε)+O(1), which follows from Alon's result. 4) We study the number of EPR pairs required to be shared in an entanglement-assisted one-way protocol. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix.