Quantum algorithms for diverse problems, including search and optimization problems, require the implementation of a reflection operator over a target state. Commonly, such reflections are approximately implemented using phase estimation. Here we use a linear combination of unitaries and a version of amplitude amplification to approximate reflection operators over eigenvectors of unitary operators using exponentially less ancillary qubits in terms of a precision parameter. The gate complexity of our method is also comparable to that of the phase estimation approach in a certain limit of interest. Like phase estimation, our method requires the implementation of controlled unitary operations. We then extend our results to the Hamiltonian case where the target state is an eigenvector of a Hamiltonian whose matrix elements can be queried. Our results are useful in that they reduce the resources required by various quantum algorithms in the literature. Our improvements also rely on an efficient quantum algorithm to prepare a quantum state with Gaussian-like amplitudes that may be of independent interest. We also provide a lower bound on the query complexity of implementing approximate reflection operators on a quantum computer.
Quantum algorithms for diverse problems, including search and optimization problems, require the implementation of a reflection operator over a target state. Commonly, such reflections are approximately implemented using phase estimation. Here we use a linear combination of unitaries and a version of amplitude amplification to approximate reflection operators over eigenvectors of unitary operators using exponentially less ancillary qubits in terms of a precision parameter. The gate complexity of our method is also comparable to that of the phase estimation approach in a certain limit of interest. Like phase estimation, our method requires the implementation of controlled unitary operations. We then extend our results to the Hamiltonian case where the target state is an eigenvector of a Hamiltonian whose matrix elements can be queried. Our results are useful in that they reduce the resources required by various quantum algorithms in the literature. Our improvements also rely on an efficient quantum algorithm to prepare a quantum state with Gaussian-like amplitudes that may be of independent interest. We also provide a lower bound on the query complexity of implementing approximate reflection operators on a quantum computer.
We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.
Finding a good approximation of the top eigenvector of a given d×d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity O~(d1.75) and one with time complexity d1.5+o(1) (the first algorithm has a slightly better dependence on the ℓ2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω(d2) queries to entries of A, and hence Ω(d2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd1.5+o(1). We also prove a nearly-optimal lower bound of Ω~(d1.5) on the quantum query complexity of approximating the top eigenvector. Our quantum algorithms run a version of the classical power method that is robust to certain benign kinds of errors, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer, in different ways for the two algorithms. Our first algorithm estimates the matrix-vector product one entry at a time, using a new "Gaussian phase estimation" procedure. Our second algorithm uses block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography procedure.
The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.
We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. We characterize the query complexity for obtaining Schatten q-norm estimates of a rank-r mixed state, up to polylogarithmic factors. In particular, we show that a trace-norm (q = 1) estimate can be obtained with queries. This improves (assuming our stronger input model) the ε-dependence over the works of O'Donnell and Wright (STOC 2016) and Haah et al. (IEEE Trans. Inf. Theory, 63.9, 2017), that use a joint measurement on copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can require a large amount of computing resources. We describe sample-optimal algorithms for pure states that are simple and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al. (arXiv:2111.09283) when the measurement operators do not fully overlap. More specifically, we show that for E1,…, Em normalized measurement operators, all expectation values Tr(Ejρ) can be efficiently learned up to error ε with applications of a state-preparation unitary for a purification of ρ. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08800
The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.
Gaussian states hold a fundamental place in quantum mechanics, quantum information, and quantum computing. Many subfields, including quantum simulation of continuousvariable systems, quantum chemistry, and quantum machine learning, rely on the ability to accurately and efficiently prepare states that reflect a Gaussian profile in their probability amplitudes. Although Gaussian states are natural in continuousvariable systems, the practical interest in digital, gate-based quantum computers demands discrete approximations of Gaussian distributions over a computational basis of size2n. Because of the exponential scaling of naive amplitude-encoding approaches and the cost of certain block-encoding or Hamiltonian simulation techniques, a resource-efficient preparation of approximate Gaussian states is required. In this work, we propose and analyze a circuit-based approach that starts with singlequbit rotations to form an exponential amplitude profile and then applies the quantum Fourier transform to map those amplitudes into an approximate Gaussian distribution. We demonstrate that this procedure achieves high fidelity with the target Gaussian state while allowing optional pruning of small controlled-phase angles in the quantum Fourier transform, thus reducing gate complexity to near-linear inO(n). We conclude that the proposed technique is a promising route to make Gaussian states accessible on noisy quantum hardware and to pave the way for scalable implementations on future devices. The implementation of this algorithm is available at the Classiq library: https://github.com/classiq/classiq-library.