01422nas a2200145 4500008004100000245007300041210006900114260001400183490000600197520097400203100002301177700001801200700002101218856003701239 2021 eng d00aHigh-precision quantum algorithms for partial differential equations0 aHighprecision quantum algorithms for partial differential equati c11/4/20210 v53 a
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.
1 aChilds, Andrew, M.1 aLiu, Jin-Peng1 aOstrander, Aaron uhttps://arxiv.org/abs/2002.0786801284nas a2200145 4500008004100000245004700041210004700088260001500135490000600150520088800156100002301044700002101067700001301088856003701101 2019 eng d00aFaster quantum simulation by randomization0 aFaster quantum simulation by randomization c08/28/20190 v33 aProduct 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.
1 aChilds, Andrew, M.1 aOstrander, Aaron1 aSu, Yuan uhttps://arxiv.org/abs/1805.0838501091nas a2200145 4500008004100000245005500041210005500096260001500151490000800166520066600174100002300840700002400863700002100887856003700908 2019 eng d00aQuantum Algorithm for Simulating the Wave Equation0 aQuantum Algorithm for Simulating the Wave Equation c03/24/20190 v99 3 aWe 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.
1 aCosta, Pedro, C.S.1 aJordan, Stephen, P.1 aOstrander, Aaron uhttps://arxiv.org/abs/1711.0539401082nas a2200181 4500008004100000022001400041245007000055210006900125260001500194300001400209490000700223520042300230100001800653700002100671700002100692700001600713856017100729 2017 eng d a1944-417600aDomination with decay in triangular matchstick arrangement graphs0 aDomination with decay in triangular matchstick arrangement graph c2017/05/14 a749 - 7660 v103 aWe 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.
1 aCochran, Jill1 aHenderson, Terry1 aOstrander, Aaron1 aTaylor, Ron uhttp://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.pdf01429nas a2200169 4500008004100000245010800041210006900149260001500218300001400233490000800247520088200255100002301137700002301160700002101183700001801204856003701222 2017 eng d00aQuantum algorithm for linear differential equations with exponentially improved dependence on precision0 aQuantum algorithm for linear differential equations with exponen c2017/12/01 a1057-10810 v3563 aWe 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.
1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aOstrander, Aaron1 aWang, Guoming uhttps://arxiv.org/abs/1701.0368400689nas a2200157 4500008004100000022001400041245006100055210006100116260001500177300001400192490000800206520020400214653002100418100002100439856007100460 2015 eng d a0024-379500aLaplacian matrices and Alexandrov topologies of digraphs0 aLaplacian matrices and Alexandrov topologies of digraphs c2015/09/15 a174 - 1850 v4813 aWe 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.10aLaplacian matrix1 aOstrander, Aaron uhttp://www.sciencedirect.com/science/article/pii/S002437951500284001231nas a2200145 4500008004100000245014400041210006900185260001500254300001100269490000700280520070100287100002100988700002101009856005501030 2014 eng d00aExtended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model in an oscillating field0 aExtended order parameter and conjugate field for the dynamic pha c2014/02/12 a0221140 v893 aWe 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.1 aRobb, Daniel, T.1 aOstrander, Aaron uhttp://link.aps.org/doi/10.1103/PhysRevE.89.02211400860nas a2200169 4500008004100000245005600041210005600097260001500153300001100168490000700179520036800186100002100554700001900575700002400594700001700618856005500635 2012 eng d00aGluon chain formation in presence of static charges0 aGluon chain formation in presence of static charges c2012/12/10 a1140150 v863 aWe 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.1 aOstrander, Aaron1 aSantopinto, E.1 aSzczepaniak, A., P.1 aVassallo, A. uhttp://link.aps.org/doi/10.1103/PhysRevD.86.11401500871nas a2200157 4500008004100000245006300041210006200104260001500166490000700181520037400188100001900562700002200581700002100603700001900624856007000643 2012 eng d00aNon-Recursively Constructible Recursive Families of Graphs0 aNonRecursively Constructible Recursive Families of Graphs c2012/04/160 v193 aIn 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.1 aBouey, Colleen1 aGraves, Christina1 aOstrander, Aaron1 aPalma, Gregory uhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/2211