arXiv:quant-ph/0512238

Efficient Preparation of Quantum States With Exponential Precision

Péter Jaksch

Published Dec 27, 2005• 0 citations

Abstract

It has been shown that, starting from the state |0>, in the general case, an arbitrary quantum state |ψ> cannot be prepared with exponential precision in polynomial time. However, we show that for the important special case when |ψ> represents discrete values of some real, continuous function ψ(x), efficient preparation is possible by applying the eigenvalue estimation algorithm to a Hamiltonian which has ψ(x) as an eigenstate. We construct the required Hamiltonian explicitly and present an iterative algorithm for removing unwanted superpositions from the output state in order to reach |ψ> within exponential accuracy. The method works under very general conditions and can be used to provide the quantum simulation algorithm with very accurate and general starting states.

DOI: 10.48550/arxiv.quant-ph/0512238

Related papers

Eigenvector Approximation Leading to Exponential Speedup of Quantum Eigenvalue Calculation

Péter Jaksch, Anargyros Papageorgiou

We present an efficient method for preparing the initial state required by the eigenvalue approximation quantum algorithm of Abrams and Lloyd. Our method can be applied when solving continuous Hermitian eigenproblems, e.g., the Schrödinger equation, on a discrete grid. We start with a classically obtained eigenvector for a problem discretized on a coarse grid, and we efficiently construct, quantum mechanically, an approximation of the same eigenvector on a fine grid. We use this approximation as the initial state for the eigenvalue estimation algorithm, and show the relationship between its success probability and the size of the coarse grid.

arXiv:quant-ph/0308016Physical Review LettersDec 19, 200343 citations

Exact and efficient Lanczos method on a quantum computer

William Kirby, Mário Motta, Antonio Mezzacapo

We present an algorithm that uses block encoding on a quantum computer to exactly construct a Krylov space, which can be used as the basis for the Lanczos method to estimate extremal eigenvalues of Hamiltonians. While the classical Lanczos method has exponential cost in the system size to represent the Krylov states for quantum systems, our efficient quantum algorithm achieves this in polynomial time and memory. The construction presented is exact in the sense that the resulting Krylov space is identical to that of the Lanczos method, so the only approximation with respect to the exact method is due to finite sample noise. This is possible because, unlike previous quantum Krylov methods, our algorithm does not require simulating real or imaginary time evolution. We provide an explicit error bound for the resulting ground state energy estimate in the presence of noise. For our method to be successful efficiently, the only requirement on the input problem is that the overlap of the initial state with the true ground state must be Ω ( 1 / poly ( n ) ) for n qubits.

arXiv:2208.00567QuantumMay 23, 202366 citations

Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions

Adam A. Holmes, A. Y. Matsuura

Effective quantum computation relies upon making good use of the exponential information capacity of a quantum machine. A large barrier to designing quantum algorithms for execution on real quantum machines is that, in general, it is intractably difficult to construct an arbitrary quantum state to high precision. Many quantum algorithms rely instead upon initializing the machine in a simple state, and evolving the state through an efficient (i.e. at most polynomial-depth) quantum algorithm. In this work, we show that there exist families of quantum states that can be prepared to high precision with circuits of linear size and depth. We focus on real-valued, smooth, differentiable functions with bounded derivatives on a domain of interest, exemplified by commonly used probability distributions. We further develop an algorithm that requires only linear classical computation time to generate accurate linear- depth circuits to prepare these states, and apply this to well-known and heavily-utilized functions including Gaussian and lognormal distributions. Our procedure rests upon the quantum state representation tool known as the matrix product state (MPS). By efficiently and scalably encoding an explicit amplitude function into an MPS, a high fidelity, linear-depth circuit can directly be generated. These results enable the execution of many quantum algorithms that, aside from initialization, are otherwise depth-efficient.

arXiv:2005.04351IEEE International Conference on Quantum Computing and Engineering (QCE)Oct 1, 202053 citations

Quantum eigenvalue estimation via time series analysis

Rolando D. Somma

Abstract We present an efficient method for estimating the eigenvalues of a Hamiltonian H from the expectation values of the evolution operator for various times. For a given quantum state ρ , our method outputs a list of eigenvalue estimates and approximate probabilities. Each probability depends on the support of ρ in those eigenstates of H associated with eigenvalues within an arbitrarily small range. The complexity of our method is polynomial in the inverse of a given precision parameter ϵ , which is the gap between eigenvalue estimates. Unlike the well-known quantum phase estimation algorithm that uses the quantum Fourier transform, our method does not require large ancillary systems, large sequences of controlled operations, or preserving coherence between experiments, and is therefore more attractive for near-term applications. The output of our method can be used to estimate spectral properties of H and other expectation values efficiently, within additive error proportional to ϵ .

arXiv:1907.11748New Journal of PhysicsNov 27, 2019142 citations

Preparing Arbitrary Continuous Functions in Quantum Registers With Logarithmic Complexity

Arthur G. Rattew, Bálint Koczor

Quantum computers will be able solve important problems with significant polynomial and exponential speedups over their classical counterparts, for instance in option pricing in finance, and in real-space molecular chemistry simulations. However, key applications can only achieve their potential speedup if their inputs are prepared efficiently. We effectively solve the important problem of efficiently preparing quantum states following arbitrary continuous (as well as more general) functions with complexity logarithmic in the desired resolution, and with rigorous error bounds. This is enabled by the development of a fundamental subroutine based off of the simulation of rank-1 projectors. Combined with diverse techniques from quantum information processing, this subroutine enables us to present a broad set of tools for solving practical tasks, such as state preparation, numerical integration of Lipschitz continuous functions, and superior sampling from probability density functions. As a result, our work has significant implications in a wide range of applications, for instance in financial forecasting, and in quantum simulation.

arXiv:2205.00519May 1, 202212 citations

Quantum simulation of Hamiltonian eigenstates

Riccardo Manenti, Mário Motta

Abstract In this chapter, we present quantum algorithms to approximate Hamiltonian eigenstates. We start discussing the quantum phase estimation algorithms, an important subroutine that allows us to approximate eigenpairs of a Hamiltonian operator given an initial guess and a quantum circuit implementing the time evolution operator. We then present the adiabatic state preparation, a technique to transform the ground state of a Hamiltonian into the ground state of another Hamiltonian. We describe two important heuristic methods, the quantum approximate optimization algorithm, and the variational quantum eigensolver. The second part of the chapter discusses concrete applications in the field of quantum chemistry. After introducing the Born-Oppenheimer Hamiltonian in second quantization and the Hartree-Fock method, we illustrate how a chemical problem can be mapped onto a quantum computer. We conclude the chapter with the simulation of the hydrogen molecule in a minimal basis with the iterative phase estimation algorithm.

Aug 25, 20230 citations