More Like this

1. Automatically Translating Quantum Programs from a Subset of Common Gates to an Adiabatic Representation

   https://doi.org/10.1007/978-3-030-21500-2_9  

   Regan M., Eastwood B. ( May 2019 , nternational Conference on Reversible Computation (RC), Springer LNCS)

   Adiabatic computing with two degrees of freedom of 2-local Hamiltonians has been theoretically shown to be equivalent to the gate model of universal quantum computing. But today’s quantum annealers, namely D-Wave’s 2000Q platform, only provide a 2-local 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 D-Wave. The problem is of interest because gate-based quantum platforms are currently limited to 20 qubits while D-Wave 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 single-degree 2-local 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 single-degree 2-local Ising Hamiltonians, which are subsequently embedded in the D-Wave 2000Q chimera graph. Thesemore »gate elements are placed in the chimera graph and augmented by constraints that enforce inter-gate logical relationships, resulting in an annealer embedding that completely characterizes the overall gate circuit. Annealer embeddings for several example quantum gate circuits are then evaluated on D-Wave 2000Q hardware.« less
2. Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms

   https://doi.org/10.1609/aaai.v34i02.5524  

   Sahai, Tuhin ; Mishra, Anurag ; Pasini, Jose Miguel ; Jha, Susmit ( June 2020 , Proceedings of the AAAI Conference on Artificial Intelligence)

   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 maximum-satisfiability (MAX-SAT) 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 real-world scenarios, this problem is typically infeasible even when using state-of-the-art 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 annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.
3. Molecular dynamics on quantum annealers

   https://doi.org/10.1038/s41598-022-21163-x  

   Gaidai, Igor ; Babikov, Dmitri ; Teplukhin, Alexander ; Kendrick, Brian K. ; Mniszewski, Susan M. ; Zhang, Yu ; Tretiak, Sergei ; Dub, Pavel A. ( October 2022 , Scientific Reports)

   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 D-Wave 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 post-processing (greedy algorithm). Importantly, the QDE framework developed here is entirely general and can be applied to solve any system of first-order ordinary nonlinear differential equations using a quantum annealer.
4. Quantum simulation of real-space dynamics

   https://doi.org/10.22331/q-2022-11-17-860  

   Childs, Andrew M. ; Leng, Jiaqi ; Li, Tongyang ; Liu, Jin-Peng ; Zhang, Chenyi ( November 2022 , Quantum)

   Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space 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 higher-order derivatives of the wave function, and F measures the time-integrated 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 two-qubit gates,more »and another using η 3 ( 4 d ) d / 2 T poly ( log ⁡ ( η d T g ′ / ( Δ ϵ ) ) ) / Δ one- and two-qubit gates and QRAM operations, where T is the evolution time and the parameter Δ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.« less
5. Edge Expansion and Spectral Gap of Nonnegative Matrices

   https://doi.org/10.1137/1.9781611975994.73  

   Mehta, Jenish C. ; Schulman, Leonard J. ( January 2020 , Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms)

   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 »factor of $n^{\alpha}$ for $\frac{1}{2}\leq\alpha\leq1$ in lower bounding $\phi$ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices $R$ with nonnegative entries, to obtain a two-sided \emph{gapped} refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such $R$, there is a nonnegative eigenvalue $r$ such that all eigenvalues of $R$ lie within the closed disk of radius $r$ about $0$. Further, if $R$ is irreducible, which means $\phi(R)>0$ (for suitably defined $\phi$), then $r$ is positive and all other eigenvalues lie within the \textit{open} disk, so (with eigenvalues sorted by real part), $\re\lambda_{2}(R)« less