%0 Journal Article %J Quantum 5, 574 %D 2021 %T High-precision quantum algorithms for partial differential equations %A Andrew M. Childs %A Jin-Peng Liu %A Aaron Ostrander %X
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ε), where ε is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ε)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
%B Quantum 5, 574 %V 5 %8 11/4/2021 %G eng %U https://arxiv.org/abs/2002.07868 %N 574 %R https://doi.org/10.22331/q-2021-11-10-574 %0 Journal Article %J Quantum %D 2019 %T Faster quantum simulation by randomization %A Andrew M. Childs %A Aaron Ostrander %A Yuan Su %XProduct formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly efficient. We show that by simply randomizing how the summands are ordered, one can prove stronger bounds on the quality of approximation and thereby give more efficient simulations. Indeed, we show that these bounds can be asymptotically better than previous bounds that exploit commutation between the summands, despite using much less information about the structure of the Hamiltonian. Numerical evidence suggests that our randomized algorithm may be advantageous even for near-term quantum simulation.
%B Quantum %V 3 %8 08/28/2019 %G eng %U https://arxiv.org/abs/1805.08385 %N 182 %R https://doi.org/10.22331/q-2019-09-02-182 %0 Journal Article %J Phys. Rev. A %D 2019 %T Quantum Algorithm for Simulating the Wave Equation %A Pedro C.S. Costa %A Stephen P. Jordan %A Aaron Ostrander %XWe present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. It relies on factorizations of discretized Laplacian operators to allow for improved scaling in truncation errors and improved scaling for state preparation relative to general purpose linear differential equation algorithms. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell's equations.
%B Phys. Rev. A %V 99 %8 03/24/2019 %G eng %U https://arxiv.org/abs/1711.05394 %N 012323 %R https://doi.org/10.1103/PhysRevA.99.012323 %0 Journal Article %J Involve, a Journal of Mathematics %D 2017 %T Domination with decay in triangular matchstick arrangement graphs %A Jill Cochran %A Terry Henderson %A Aaron Ostrander %A Ron Taylor %XWe provide results for the exponential dominating numbers and total exponential dominating numbers of a family of triangular grid graphs. We then prove inequalities for these numbers and compare them with inequalities that hold more generally for exponential dominating numbers of graphs.
%B Involve, a Journal of Mathematics %V 10 %P 749 - 766 %8 2017/05/14 %G eng %U http://msp.org/involve/http://msp.org/involve/2017/10-5/index.xhtmlhttp://msp.org/involve/2017/10-5/p03.xhtmlhttp://msp.org/involve/2017/10-5/involve-v10-n5-p03-s.pdf %N 5 %! Involve %R 10.2140/involve10.2140/involve.2017.10-510.2140/involve.2017.10.749 %0 Journal Article %J Communications in Mathematical Physics %D 2017 %T Quantum algorithm for linear differential equations with exponentially improved dependence on precision %A Dominic W. Berry %A Andrew M. Childs %A Aaron Ostrander %A Guoming Wang %XWe present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.
%B Communications in Mathematical Physics %V 356 %P 1057-1081 %8 2017/12/01 %G eng %U https://arxiv.org/abs/1701.03684 %N 3 %0 Journal Article %J Linear Algebra and its Applications %D 2015 %T Laplacian matrices and Alexandrov topologies of digraphs %A Aaron Ostrander %K Laplacian matrix %X We explore the spectral properties of digraph Laplacians and how they relate to topological properties of digraphs (such as openness, closure, and strong connectedness) under the Alexandrov topology. %B Linear Algebra and its Applications %V 481 %P 174 - 185 %8 2015/09/15 %G eng %U http://www.sciencedirect.com/science/article/pii/S0024379515002840 %R http://dx.doi.org/10.1016/j.laa.2015.04.031 %0 Journal Article %J Physical Review E %D 2014 %T Extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model in an oscillating field %A Daniel T. Robb %A Aaron Ostrander %X We present numerical evidence for an extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model driven by an oscillating field. The order parameter, previously taken to be the time-averaged magnetization, comprises the deviations of the Fourier components of the magnetization from their values at the critical period. The conjugate field, previously taken to be the time-averaged magnetic field, comprises the even Fourier components of the field. The scaling exponents β and δ associated with the extended order parameter and conjugate field are shown numerically to be consistent with their values in the equilibrium mean-field model. %B Physical Review E %V 89 %P 022114 %8 2014/02/12 %G eng %U http://link.aps.org/doi/10.1103/PhysRevE.89.022114 %R 10.1103/PhysRevE.89.022114 %0 Journal Article %J Physical Review D %D 2012 %T Gluon chain formation in presence of static charges %A Aaron Ostrander %A Santopinto, E. %A Szczepaniak, A. P. %A Vassallo, A. %X We consider the origins of the gluon chain model. The model serves as a realization of the dynamics of the chromoelectric flux between static quark-antiquark sources. The derivation is based on the large-NC limit of the Coulomb gauge Hamiltonian in the presence of a background field introduced to model magnetic charge condensation inducing electric confinement. %B Physical Review D %V 86 %P 114015 %8 2012/12/10 %G eng %U http://link.aps.org/doi/10.1103/PhysRevD.86.114015 %R 10.1103/PhysRevD.86.114015 %0 Journal Article %J The Electronic Journal of Combinatorics %D 2012 %T Non-Recursively Constructible Recursive Families of Graphs %A Colleen Bouey %A Christina Graves %A Aaron Ostrander %A Gregory Palma %X In a publication by Noy and Ribó, it was shown that recursively constructible families of graphs are recursive. The authors also conjecture that the converse holds; that is, recursive families are also recursively constructible. In this paper, we provide two specific counterexamples to this conjecture, which we then extend to an infinite family of counterexamples. %B The Electronic Journal of Combinatorics %V 19 %8 2012/04/16 %G eng %U http://www.combinatorics.org/ojs/index.php/eljc/article/view/2211 %N 2