TY - JOUR T1 - High-precision quantum algorithms for partial differential equations JF - Quantum 5, 574 Y1 - 2021 A1 - Andrew M. Childs A1 - Jin-Peng Liu A1 - Aaron Ostrander AB -
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.
VL - 5 UR - https://arxiv.org/abs/2002.07868 CP - 574 U5 - https://doi.org/10.22331/q-2021-11-10-574 ER - TY - JOUR T1 - Faster quantum simulation by randomization JF - Quantum Y1 - 2019 A1 - Andrew M. Childs A1 - Aaron Ostrander A1 - Yuan Su AB -Product 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.
VL - 3 UR - https://arxiv.org/abs/1805.08385 CP - 182 U5 - https://doi.org/10.22331/q-2019-09-02-182 ER - TY - JOUR T1 - Quantum Algorithm for Simulating the Wave Equation JF - Phys. Rev. A Y1 - 2019 A1 - Pedro C.S. Costa A1 - Stephen P. Jordan A1 - Aaron Ostrander AB -We 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.
VL - 99 UR - https://arxiv.org/abs/1711.05394 CP - 012323 U5 - https://doi.org/10.1103/PhysRevA.99.012323 ER - TY - JOUR T1 - Domination with decay in triangular matchstick arrangement graphs JF - Involve, a Journal of Mathematics Y1 - 2017 A1 - Jill Cochran A1 - Terry Henderson A1 - Aaron Ostrander A1 - Ron Taylor AB -We 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.
VL - 10 U4 - 749 - 766 UR - 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 CP - 5 J1 - Involve U5 - 10.2140/involve10.2140/involve.2017.10-510.2140/involve.2017.10.749 ER - TY - JOUR T1 - Quantum algorithm for linear differential equations with exponentially improved dependence on precision JF - Communications in Mathematical Physics Y1 - 2017 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Aaron Ostrander A1 - Guoming Wang AB -We 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.
VL - 356 U4 - 1057-1081 UR - https://arxiv.org/abs/1701.03684 CP - 3 ER - TY - JOUR T1 - Laplacian matrices and Alexandrov topologies of digraphs JF - Linear Algebra and its Applications Y1 - 2015 A1 - Aaron Ostrander KW - Laplacian matrix AB - 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. VL - 481 U4 - 174 - 185 UR - http://www.sciencedirect.com/science/article/pii/S0024379515002840 U5 - http://dx.doi.org/10.1016/j.laa.2015.04.031 ER - TY - JOUR T1 - Extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model in an oscillating field JF - Physical Review E Y1 - 2014 A1 - Daniel T. Robb A1 - Aaron Ostrander AB - 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. VL - 89 U4 - 022114 UR - http://link.aps.org/doi/10.1103/PhysRevE.89.022114 U5 - 10.1103/PhysRevE.89.022114 ER - TY - JOUR T1 - Gluon chain formation in presence of static charges JF - Physical Review D Y1 - 2012 A1 - Aaron Ostrander A1 - Santopinto, E. A1 - Szczepaniak, A. P. A1 - Vassallo, A. AB - 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. VL - 86 U4 - 114015 UR - http://link.aps.org/doi/10.1103/PhysRevD.86.114015 U5 - 10.1103/PhysRevD.86.114015 ER - TY - JOUR T1 - Non-Recursively Constructible Recursive Families of Graphs JF - The Electronic Journal of Combinatorics Y1 - 2012 A1 - Colleen Bouey A1 - Christina Graves A1 - Aaron Ostrander A1 - Gregory Palma AB - 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. VL - 19 UR - http://www.combinatorics.org/ojs/index.php/eljc/article/view/2211 CP - 2 ER -