 Award ID(s):
 1920523
 Publication Date:
 NSFPAR ID:
 10220273
 Journal Name:
 Physical Chemistry Chemical Physics
 Volume:
 22
 Issue:
 45
 Page Range or eLocationID:
 26136 to 26144
 ISSN:
 14639076
 Sponsoring Org:
 National Science Foundation
More Like this

Adiabatic computing with two degrees of freedom of 2local Hamiltonians has been theoretically shown to be equivalent to the gate model of universal quantum computing. But today’s quantum annealers, namely DWave’s 2000Q platform, only provide a 2local Ising Hamiltonian abstraction with a single degree of freedom. This raises the question what subset of gate programs can be expressed as quadratic unconstrained binary problems (QUBOs) on the DWave. The problem is of interest because gatebased quantum platforms are currently limited to 20 qubits while DWave provides 2,000 qubits. However, when transforming entire gate circuits into QUBOs, additional qubits will be required. The objective of this work is to determine a subset of quantum gates suitable for transformation into singledegree 2local Ising Hamiltonians under a common qubit base representation such that they comprise a compound circuit suitable for pure quantum computation, i.e., without having to switch between classical and quantum computing for different bases. To this end, this work contributes, for the first time, a fully automated method to translate quantum gate circuits comprised of a subset of common gates expressed as an IBM Qiskit program to singledegree 2local Ising Hamiltonians, which are subsequently embedded in the DWave 2000Q chimera graph. Thesemore »

Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximumsatisfiability (MAXSAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in realworld scenarios, this problem is typically infeasible even when using stateoftheart algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealingbased solutions. We present the overall approach and compare results from the DWave quantum annealer against the bestknown classical algorithms such as the Hamzede FreitasSelby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.

Abstract In this work we demonstrate a practical prospect of using quantum annealers for simulation of molecular dynamics. A methodology developed for this goal, dubbed Quantum Differential Equations (QDE), is applied to propagate classical trajectories for the vibration of the hydrogen molecule in several regimes: nearly harmonic, highly anharmonic, and dissociative motion. The results obtained using the DWave 2000Q quantum annealer are all consistent and quickly converge to the analytical reference solution. Several alternative strategies for such calculations are explored and it was found that the most accurate results and the best efficiency are obtained by combining the quantum annealer with classical postprocessing (greedy algorithm). Importantly, the QDE framework developed here is entirely general and can be applied to solve any system of firstorder ordinary nonlinear differential equations using a quantum annealer.

Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finitedimensional systems, less is known about quantum algorithms for realspace dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a d dimensional Schrödinger equation with η particles can be simulated with gate complexity O ~ ( η d F poly ( log ( g ′ / ϵ ) ) ) , where ϵ is the discretization error, g ′ controls the higherorder derivatives of the wave function, and F measures the timeintegrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on ϵ and g ′ from poly ( g ′ / ϵ ) to poly ( log ( g ′ / ϵ ) ) and polynomially improves the dependence on T and d , while maintaining best known performance with respect to η . For the case of Coulomb interactions, we give an algorithm using η 3 ( d + η ) T poly ( log ( η d T g ′ / ( Δ ϵ ) ) ) / Δ one and twoqubit gates,more »

The classic graphical Cheeger inequalities state that if $M$ is an $n\times n$ \emph{symmetric} doubly stochastic matrix, then \[ \frac{1\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1\lambda_{2}(M))} \] where $\phi(M)=\min_{S\subseteq[n],S\leq n/2}\left(\frac{1}{S}\sum_{i\in S,j\not\in S}M_{i,j}\right)$ is the edge expansion of $M$, and $\lambda_{2}(M)$ is the second largest eigenvalue of $M$. We study the relationship between $\phi(A)$ and the spectral gap $1\re\lambda_{2}(A)$ for \emph{any} doubly stochastic matrix $A$ (not necessarily symmetric), where $\lambda_{2}(A)$ is a nontrivial eigenvalue of $A$ with maximum real part. Fiedler showed that the upper bound on $\phi(A)$ is unaffected, i.e., $\phi(A)\leq\sqrt{2\cdot(1\re\lambda_{2}(A))}$. With regards to the lower bound on $\phi(A)$, there are known constructions with \[ \phi(A)\in\Theta\left(\frac{1\re\lambda_{2}(A)}{\log n}\right), \] indicating that at least a mild dependence on $n$ is necessary to lower bound $\phi(A)$. In our first result, we provide an \emph{exponentially} better construction of $n\times n$ doubly stochastic matrices $A_{n}$, for which \[ \phi(A_{n})\leq\frac{1\re\lambda_{2}(A_{n})}{\sqrt{n}}. \] In fact, \emph{all} nontrivial eigenvalues of our matrices are $0$, even though the matrices are highly \emph{nonexpanding}. We further show that this bound is in the correct range (up to the exponent of $n$), by showing that for any doubly stochastic matrix $A$, \[ \phi(A)\geq\frac{1\re\lambda_{2}(A)}{35\cdot n}. \] As a consequence, unlike the symmetric case, there is a (necessary) loss of amore »