The Experts below are selected from a list of 58731 Experts worldwide ranked by ideXlab platform
Robin Kothari - One of the best experts on this subject based on the ideXlab platform.
-
Quantum Algorithm for simulating real time evolution of lattice hamiltonians
Foundations of Computer Science, 2018Co-Authors: Jeongwan Haah, Matthew B Hastings, Robin KothariAbstract:We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and encompasses all physically reasonable Hamiltonians. Our Algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error e using O(T polylog(nT/e)) gates with depth O(T polylog(nT/e)). Our Algorithm is the first simulation Algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/e. Our Algorithm also readily generalizes to time-dependent Hamiltonians and yields an Algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any Quantum Algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires (nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our Algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our Algorithm when the Hamiltonian is close to commuting.
-
Quantum Algorithm for simulating real time evolution of lattice hamiltonians
arXiv: Quantum Physics, 2018Co-Authors: Jeongwan Haah, Matthew B Hastings, Robin Kothari, Guang Hao LowAbstract:We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our Algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using $\mathcal O( nT \mathrm{polylog} (nT/\epsilon))$ gates with depth $\mathcal O(T \mathrm{polylog} (nT/\epsilon))$. Our Algorithm is the first simulation Algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our Algorithm also readily generalizes to time-dependent Hamiltonians and yields an Algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any Quantum Algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires $\tilde \Omega(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our Algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our Algorithm when the Hamiltonian is close to commuting.
-
Quantum Algorithm for simulating real time evolution of lattice hamiltonians
arXiv: Quantum Physics, 2018Co-Authors: Jeongwan Haah, Matthew B Hastings, Robin KothariAbstract:We present a decomposition of the real time evolution operator $e^{-i T H}$ of any local Hamiltonian $H$ on lattices $\Lambda \subseteq \mathbb Z^D$ into local unitaries based on Lieb-Robinson bounds. Combining this with recent Quantum simulation Algorithms for real time evolution, we find that the resulting Quantum simulation Algorithm has gate count $\mathcal O( T n ~\mathrm{polylog} (T n/\epsilon))$ and depth $\mathcal O( T ~\mathrm{polylog}(Tn/\epsilon))$, where $n$ is the space volume or the number of qubits, $T$ is the time of evolution, and $\epsilon$ is the accuracy of the simulation in operator norm. In contrast to this, the previous best Quantum Algorithms have gate count $\mathcal O(Tn^{2} ~\mathrm{polylog} (T n/\epsilon))$. Our approach readily generalizes to time-dependent Hamiltonians as well, and yields an Algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. Finally, we also prove a matching lower bound on the gate count of such a simulation, showing that any Quantum Algorithm that can simulate a piecewise time-independent bounded local Hamiltonian in one dimension requires $\Omega(Tn / \mathrm{polylog}(Tn) )$ gates in the worst case. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms. Unlike previous Lieb-Robinson bounds, our version gives zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our Algorithm when the Hamiltonian is close to commuting.
-
Quantum Algorithm for systems of linear equations with exponentially improved dependence on precision
SIAM Journal on Computing, 2017Co-Authors: Andrew M Childs, Robin Kothari, Rolando D SommaAbstract:Harrow, Hassidim, and Lloyd [Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified $N \times N$ matrix $A$ and an $N$-dimensional vector $\vec{b}$, there is a Quantum Algorithm that outputs a Quantum state proportional to the solution of the linear system of equations $A\vec{x} = \vec{b}$. If $A$ is sparse and well-conditioned, their Algorithm runs in time ${poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an Algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our Algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the Quantum phase estimation Algorithm, whose dependence on $\epsilon$ is prohibitive.
-
Quantum Algorithm for systems of linear equations with exponentially improved dependence on precision
arXiv: Quantum Physics, 2015Co-Authors: Andrew M Childs, Robin Kothari, Rolando D SommaAbstract:Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a Quantum Algorithm that outputs a Quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their Algorithm runs in time $\mathrm{poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an Algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our Algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the Quantum phase estimation Algorithm, whose dependence on $\epsilon$ is prohibitive.
Ben W Reichardt - One of the best experts on this subject based on the ideXlab platform.
-
Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009Co-Authors: Ben W ReichardtAbstract:The general adversary bound is a semi-definite program (SDP) that lower-bounds the Quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a Quantum walk Algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal "witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a Quantum Algorithm for evaluating span programs with only a logarithmic query overhead on the witness size. The first result is motivated by a Quantum Algorithm for evaluating composed span programs. The Algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal Quantum Algorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result extends span programs' applicability beyond the formula-evaluation problem. We extend the analysis of the Quantum Algorithm for evaluating span programs. The previous analysis shows that a corresponding bipartite graph has a large spectral gap, but only works when applied to the composition of constant-size span programs. We show generally that properties of eigenvalue-zero eigenvectors in fact imply an "effective" spectral gap around zero. A strong universality result for span programs follows. A good Quantum query Algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs are a promising model for developing more Quantum Algorithms.
-
span program based Quantum Algorithm for evaluating formulas
arXiv: Quantum Physics, 2007Co-Authors: Ben W Reichardt, Robert SpalekAbstract:We give a Quantum Algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The Algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. The main new tool is a correspondence between a classical linear-algebraic model of computation, "span programs," and weighted bipartite graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A Quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. In contrast, our Algorithm generalizes the optimal Quantum AND-OR formula evaluation Algorithm and is optimal for evaluating the balanced ternary majority formula.
Seth Lloyd - One of the best experts on this subject based on the ideXlab platform.
-
Quantum Algorithm for data fitting
Physical Review Letters, 2012Co-Authors: Nathan Wiebe, Daniel Braun, Seth LloydAbstract:We provide a new Quantum Algorithm that efficiently determines the quality of a least-squares fit over an exponentially large data set by building upon an Algorithm for solving systems of linear equations efficiently [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)]. In many cases, our Algorithm can also efficiently find a concise function that approximates the data to be fitted and bound the approximation error. In cases where the input data are pure Quantum states, the Algorithm can be used to provide an efficient parametric estimation of the Quantum state and therefore can be applied as an alternative to full Quantum-state tomography given a fault tolerant Quantum computer.
-
Quantum Algorithm for linear systems of equations
Physical Review Letters, 2009Co-Authors: Aram W Harrow, Avinatan Hassidim, Seth LloydAbstract:: Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b(-->), find a vector x(-->) such that Ax(-->) = b(-->). We consider the case where one does not need to know the solution x(-->) itself, but rather an approximation of the expectation value of some operator associated with x(-->), e.g., x(-->)(dagger) Mx(-->) for some matrix M. In this case, when A is sparse, N x N and has condition number kappa, the fastest known classical Algorithms can find x(-->) and estimate x(-->)(dagger) Mx(-->) in time scaling roughly as N square root(kappa). Here, we exhibit a Quantum Algorithm for estimating x(-->)(dagger) Mx(-->) whose runtime is a polynomial of log(N) and kappa. Indeed, for small values of kappa [i.e., poly log(N)], we prove (using some common complexity-theoretic assumptions) that any classical Algorithm for this problem generically requires exponentially more time than our Quantum Algorithm.
-
Quantum Algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
Physical Review Letters, 1999Co-Authors: Daniel S Abrams, Seth LloydAbstract:We describe a new polynomial time Quantum Algorithm that uses the Quantum fast Fourier transform to find eigenvalues and eigenvectors of a local Hamiltonian, and that can be applied in cases (commonly found in ab initio physics and chemistry problems) for which all known classical Algorithms require exponential time. Applications of the Algorithm to specific problems are considered, and we find that classically intractable and interesting problems from atomic physics may be solved with between 50 and 100 Quantum bits.
-
Experimental realization of a Quantum Algorithm
Nature, 1998Co-Authors: Isaac L Chuang, L M K Vandersypen, X Zhou, Debbie W. Leung, Seth LloydAbstract:Quantum computers^ 1 , 2 , 3 , 4 , 5 can in principle exploit Quantum-mechanical effects to perform computations (such as factoring large numbers or searching an unsorted database) more rapidly than classical computers^ 1 ,^ 2 ,^ 6 , 7 , 8 . But noise, loss of coherence, and manufacturing problems make constructing large-scale Quantum computers difficult^ 9 , 10 , 11 , 12 , 13 . Although ion traps and optical cavities offer promising experimental approaches^ 14 ,^ 15 , no Quantum Algorithm has yet been implemented with these systems. Here we report the experimental realization of a Quantum Algorithm using a bulk nuclear magnetic resonance technique^ 16 , 17 , 18 , in which the nuclear spins act as ‘Quantum bits’^ 19 . The nuclear spins are particularly suited to this role because of their natural isolation from the environment. Our simple Quantum computer solves a purely mathematical problem in fewer steps than is possible classically, requiring fewer ‘function calls’ than a classical computer to determine the global properties of an unknown function.
-
experimental realization of a Quantum Algorithm
arXiv: Quantum Physics, 1998Co-Authors: Isaac L Chuang, L M K Vandersypen, X Zhou, Debbie Leung, Seth LloydAbstract:Nuclear magnetic resonance techniques are used to realize a Quantum Algorithm experimentally. The Algorithm allows a simple NMR Quantum computer to determine global properties of an unknown function requiring fewer function ``calls'' than is possible using a classical computer.
Jeongwan Haah - One of the best experts on this subject based on the ideXlab platform.
-
Quantum Algorithm for simulating real time evolution of lattice hamiltonians
Foundations of Computer Science, 2018Co-Authors: Jeongwan Haah, Matthew B Hastings, Robin KothariAbstract:We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and encompasses all physically reasonable Hamiltonians. Our Algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error e using O(T polylog(nT/e)) gates with depth O(T polylog(nT/e)). Our Algorithm is the first simulation Algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/e. Our Algorithm also readily generalizes to time-dependent Hamiltonians and yields an Algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any Quantum Algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires (nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our Algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our Algorithm when the Hamiltonian is close to commuting.
-
Quantum Algorithm for simulating real time evolution of lattice hamiltonians
arXiv: Quantum Physics, 2018Co-Authors: Jeongwan Haah, Matthew B Hastings, Robin Kothari, Guang Hao LowAbstract:We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our Algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using $\mathcal O( nT \mathrm{polylog} (nT/\epsilon))$ gates with depth $\mathcal O(T \mathrm{polylog} (nT/\epsilon))$. Our Algorithm is the first simulation Algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our Algorithm also readily generalizes to time-dependent Hamiltonians and yields an Algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any Quantum Algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires $\tilde \Omega(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our Algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our Algorithm when the Hamiltonian is close to commuting.
-
Quantum Algorithm for simulating real time evolution of lattice hamiltonians
arXiv: Quantum Physics, 2018Co-Authors: Jeongwan Haah, Matthew B Hastings, Robin KothariAbstract:We present a decomposition of the real time evolution operator $e^{-i T H}$ of any local Hamiltonian $H$ on lattices $\Lambda \subseteq \mathbb Z^D$ into local unitaries based on Lieb-Robinson bounds. Combining this with recent Quantum simulation Algorithms for real time evolution, we find that the resulting Quantum simulation Algorithm has gate count $\mathcal O( T n ~\mathrm{polylog} (T n/\epsilon))$ and depth $\mathcal O( T ~\mathrm{polylog}(Tn/\epsilon))$, where $n$ is the space volume or the number of qubits, $T$ is the time of evolution, and $\epsilon$ is the accuracy of the simulation in operator norm. In contrast to this, the previous best Quantum Algorithms have gate count $\mathcal O(Tn^{2} ~\mathrm{polylog} (T n/\epsilon))$. Our approach readily generalizes to time-dependent Hamiltonians as well, and yields an Algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. Finally, we also prove a matching lower bound on the gate count of such a simulation, showing that any Quantum Algorithm that can simulate a piecewise time-independent bounded local Hamiltonian in one dimension requires $\Omega(Tn / \mathrm{polylog}(Tn) )$ gates in the worst case. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms. Unlike previous Lieb-Robinson bounds, our version gives zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our Algorithm when the Hamiltonian is close to commuting.
Sabre Kais - One of the best experts on this subject based on the ideXlab platform.
-
Quantum Algorithm and circuit design solving the Poisson equation
New Journal of Physics, 2013Co-Authors: Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph F. Traub, Sabre KaisAbstract:The Poisson equation occurs in many areas of science and engineering. Here we focus on its numerical solution for an equation in d dimensions. In particular we present a Quantum Algorithm and a scalable Quantum circuit design which approximates the solution of the Poisson equation on a grid with error e. We assume we are given a superposition of function evaluations of the right-hand side of the Poisson equation. The Algorithm produces a Quantum state encoding the solution. The number of Quantum operations and the number of qubits used by the circuit is almost linear in d and polylog in e−1. We present Quantum circuit modules together with performance guarantees which can also be used for other problems.
-
Quantum Algorithm for obtaining the energy spectrum of molecular systems
arXiv: Quantum Physics, 2009Co-Authors: Hefeng Wang, Sabre Kais, Alan Aspuruguzik, Mark R HoffmannAbstract:Simulating a Quantum system is more efficient on a Quantum computer than on a classical computer. The time required for solving the Schr\"odinger equation to obtain molecular energies has been demonstrated to scale polynomially with system size on a Quantum computer, in contrast to the well-known result of exponential scaling on a classical computer. In this paper, we present a Quantum Algorithm to obtain the energy spectrum of molecular systems based on the multi-configurational self-consistent field (MCSCF) wave function. By using a MCSCF wave function as the initial guess, the excited states are accessible; Entire potential energy surfaces of molecules can be studied more efficiently than if the simpler Hartree-Fock guess was employed. We show that a small increase of the MCSCF space can dramatically increase the success probability of the Quantum Algorithm, even in regions of the potential energy surface that are far from the equilibrium geometry. For the treatment of larger systems, a multi-reference configuration interaction approach is suggested. We demonstrate that such an Algorithm can be used to obtain the energy spectrum of the water molecule.
