Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA quantum algorithm for simulating non-sparse Hamiltonians
544
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is $O(tsqrt{N}|H|,mathrm{polylog}(N, t|H|, 1/epsilon))$, where $t$ is the evolution time, $N$ is the dimension of the system, and $epsilon$ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving $widetilde{O}(sqrt{N})$ dependence for both applications.
rate research
Read More
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $epsilon$ using $Obig(tau frac{log(tau/epsilon)}{loglog(tau/epsilon)}big)$ queries and $Obig(tau frac{log^2(tau/epsilon)}{loglog(tau/epsilon)}nbig)$ additional 2-qubit gates, where $tau = d^2 |{H}|_{max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of oblivious amplitude amplification that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
We address the problem of simulating pair-interaction Hamiltonians in n node quantum networks where the subsystems have arbitrary, possibly different, dimensions. We show that any pair-interaction can be used to simulate any other by applying sequences of appropriate local control sequences. Efficient schemes for decoupling and time reversal can be constructed from orthogonal arrays. Conditions on time optimal simulation are formulated in terms of spectral majorization of matrices characterizing the coupling parameters. Moreover, we consider a specific system of n harmonic oscillators with bilinear interaction. In this case, decoupling can efficiently be achieved using the combinatorial concept of difference schemes. For this type of interactions we present optimal schemes for inversion.
Let $H$ be a fixed $k$-vertex graph with $m$ edges and minimum degree $d >0$. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$-vertex graph contains $H$ as a subgraph is $O(n^{2-2/k-t})$, where $ t = max{frac{k^2- 2(m+1)}{k(k+1)(m+1)}, frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $widetilde O(n^{2-2/k})$.
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an $n$-dimensional convex body within multiplicative error $epsilon$ using $tilde{O}(n^{3}+n^{2.5}/epsilon)$ queries to a membership oracle and $tilde{O}(n^{5}+n^{4.5}/epsilon)$ additional arithmetic operations. For comparison, the best known classical algorithm uses $tilde{O}(n^{4}+n^{3}/epsilon^{2})$ queries and $tilde{O}(n^{6}+n^{5}/epsilon^{2})$ additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of Chebyshev cooling, where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.
Ground state counting plays an important role in several applications in science and engineering, from estimating residual entropy in physical systems, to bounding engineering reliability and solving combinatorial counting problems. While quantum algorithms such as adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) can minimize Hamiltonians, they are inadequate for counting ground states. We modify AQO and QAOA to count the ground states of arbitrary classical spin Hamiltonians, including counting ground states with arbitrary nonnegative weights attached to them. As a concrete example, we show how our method can be used to count the weighted fraction of edge covers on graphs, with user-specified confidence on the relative error of the weighted count, in the asymptotic limit of large graphs. We find the asymptotic computational time complexity of our algorithms, via analytical predictions for AQO and numerical calculations for QAOA, and compare with the classical optimal Monte Carlo algorithm (OMCS), as well as a modified Grovers algorithm. We show that for large problem instances with small weights on the ground states, AQO does not have a quantum speedup over OMCS for a fixed error and confidence, but QAOA has a sub-quadratic speedup on a broad class of numerically simulated problems. Our work is an important step in approaching general ground-state counting problems beyond those that can be solved with Grovers algorithm. It offers algorithms that can employ noisy intermediate-scale quantum devices for solving ground state counting problems on small instances, which can help in identifying more problem classes with quantum speedups.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
