Given an algorithm that outputs the correct answer with bounded error, say 1 / 3 , it is sometimes desirable to reduce this error to some arbitrarily small ε – e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of O ( log 1 ε ) from calling the algorithm this many times.Transducers are a recently introduced model of quantum computation, and it is possible to reduce the “error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors.In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.Purifiers can be seen as a way of turning a “Monte Carlo'' quantum algorithm into a “Las Vegas'' quantum algorithm – a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.
Given an algorithm that outputs the correct answer with bounded error, say 1 / 3 , it is sometimes desirable to reduce this error to some arbitrarily small ε – e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of O ( log 1 ε ) from calling the algorithm this many times.Transducers are a recently introduced model of quantum computation, and it is possible to reduce the “error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors.In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.Purifiers can be seen as a way of turning a “Monte Carlo'' quantum algorithm into a “Las Vegas'' quantum algorithm – a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.
Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction e x a c t n e s s . Second, through careful accounting t h r i f t i n e s s , the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity . Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum t i m e complexity.In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, Q ( f ∘ g ) = O ( Q ( f ) ⋅ Q ( g ) ) , without log factors.We achieve this by employing a novel approach to the design of quantum algorithms based on what we call t r a n s d u c e r s , and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.
We present a technique to reduce the error probability of quantum algorithms that determine whether its input has a specified property of interest. The standard process of reducing this error is statistical processing of the results of multiple independent executions of an algorithm. Denoting by $\ensuremath{\rho}$ an upper bound of this probability (wlog; assume $\ensuremath{\rho}\ensuremath{\le}\frac{1}{2}$), classical techniques require $O(\frac{\ensuremath{\rho}}{{[(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}]}^{2}})$ executions to reduce the error to a negligible constant. We investigate when and how quantum algorithmic techniques like amplitude amplification and estimation may reduce the number of executions. On one hand, the former idea does not directly benefit algorithms that can err on both yes and no answers and the number of executions in the latter approach is $O(\frac{1}{(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}})$. We propose a quantum approach called amplitude separation that combines both these approaches and achieves $O(\frac{1}{\sqrt{1\ensuremath{-}\ensuremath{\rho}}\ensuremath{-}\sqrt{\ensuremath{\rho}}})$ executions, which betters existing approaches when the errors are high. In the multiple-weight decision problem, the input is an n-bit Boolean function f() given as a black box and the objective is to determine the number of x for which f(x)=1, denoted wt(f), given some possible values w1,...,wk for wt(f). When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using O(log2k2n) calls to f(), which shows a quadratic speedup over classical approaches and currently known quantum algorithms.
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.
Quantum error mitigation is an important technique to reduce the impact of noise in quantum computers. With more and more qubits being supported on quantum computers, there are two emerging fundamental challenges. First, the number of shots required for quantum algorithms with large numbers of qubits needs to increase in order to obtain a meaningful distribution or expected value of an observable. Second, although steady progress has been made in improving the fidelity of each qubit, circuits with a large number of qubits are likely to produce erroneous results. This low-shot, high-noise regime calls for highly scalable error mitigation techniques. In this paper, we propose a simple and effective mitigation scheme, qubit-wise majority vote, for quantum algorithms with a single correct output. We show that our scheme produces the maximum likelihood (ML) estimate under certain assumptions and bound the number of shots required. Our experimental results on real quantum devices confirm that our proposed approach requires fewer shots than existing ones, and can sometimes recover the correct answers even when they are not observed from the measurement results.
For a (possibly partial) Boolean function f:{0,1}n→{0,1} as well as a query complexity measure M which maps Boolean functions to real numbers, define the composition limit of M on f by M∗(f)=limk→∞M(fk)1/k.
We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show R0∗(f)=max{R∗(f),C∗(f)}. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability.
Along the way, we prove various combinatorial properties of measures and composition limits.
This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.