1. Computing partition functions in the one clean qubit model
    Anirban N. Chowdhury, Rolando D. Somma, Yigit Subasi

    We present a method to approximate partition functions of quantum systems using mixed-state quantum computation. For non-negative Hamiltonians, our method runs on average in time almost linear in (M/(ϵZ))^2, where M is the dimension of the quantum system, Z is the partition function, and ϵ is the relative precision. It is based on approximations of the exponential operator as linear combinations of certain operations related to block-encoding of Hamiltonians or Hamiltonian evolutions. The trace of each operation is estimated using a standard algorithm in the one clean qubit model. For large values of Z, our method may run faster than exact classical methods, whose complexities are polynomial in M. We also prove that a version of the partition function estimation problem within additive error is complete for the so-called DQC1 complexity class, suggesting that our method provides an exponential speedup. To attain the desired relative precision, we develop a procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.

  2. Quantum algorithms for conformal bootstrap
    Ning Bao and Junyu Liu
    [Nuclear Physics B]

    With the help of recent developments in quantum algorithms for semidefinite programming, we discuss the possibility for quantum speedup for the numerical conformal bootstrap in conformal field theory. We show that quantum algorithms may have significant improvement in the computational performance for several numerical bootstrap problems.

  3. Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut
    Sevag Gharibian and Ojas Parekh
    [Proceedings of APPROX 2019]

    Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-ferromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.

  4. Quantum algorithm for estimating volumes of convex bodies
    Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, Xiaodi Wu

    Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error ϵ using Õ(n^3.5 + n^2.5/ϵ) queries to a membership oracle and Õ(n^5.5+n^4.5/ϵ) additional arithmetic operations. For comparison, the best known classical algorithm uses Õ(n^4+n^3/ϵ^2) queries and Õ(n^6+n^5/ϵ^2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.

  5. Quantum eigenvalue estimation via time series analysis
    Rolando D. Somma

    We present an efficient method for estimating the eigenvalues of a Hamiltonian H from the expectation values of the evolution operator for various times. For a given quantum state ρ, our method outputs a list of eigenvalue estimates and approximate probabilities. Each probability depends on the support of ρ in those eigenstates associated with eigenvalues within an arbitrarily small range. The complexity of our method is polynomial in the inverse of a given precision parameter. Unlike the well-known quantum phase estimation algorithm that uses the quantum Fourier transform, our method does not require large ancillary systems, large sequences of controlled operations, or preserving coherence between experiments, and is therefore more attractive for near-term applications. The output of our method can be used to compute spectral properties of H and other expectation values efficiently.

  6. Time-dependent Hamiltonian simulation with L1-norm scaling
    Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe

    The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For the case of sparse Hamiltonian simulation, the gate complexity scales with the L1 norm ∫t0dτ‖H(τ)‖_max, whereas the best previous results scale with tmaxτ∈[0,t]‖H(τ)‖_max. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. By leveraging the L1-norm information, we obtain polynomial speedups for semi-classical simulations of scattering processes in quantum chemistry.

  7. Signaling and Scrambling with Strongly Long-Range Interactions
    Andrew Y. Guo, Minh C. Tran, Andrew M. Childs, Alexey V. Gorshkov, Zhe-Xuan Gong

    Strongly long-range interacting quantum systems---those with interactions decaying as a power-law 1/rα in the distance r on a D-dimensional lattice for α≤D---have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. As a first step towards rectifying this problem, we prove two new Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for α≤D/2. Our second bound pertains to generic long-range interacting spin Hamiltonians, and leads to a tight lower bound for the signaling time to extensive subsets of the system for all α<D. This result also lower-bounds the scrambling time, and suggests a path towards achieving a tight scrambling bound that can prove the long-standing fast scrambling conjecture.

  8. Sublinear quantum algorithms for training linear and kernel-based classifiers
    Tongyang Li, Shouvanik Chakrabarti, Xiaodi Wu

    We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given n d-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in Õ(n+d) time. We design sublinear quantum algorithms for the same task running in Õ(n^0.5 +d^0.5) time, a quadratic improvement in both n and d. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of n-dimensional matrix zero-sum games with optimal complexity Θ̃(n^0.5).

  9. Quantifying the magic of quantum channels 
    Xin Wang, Mark M. Wilde, Yuan Su

    To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum "magic" or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d, it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.

  10. Butterfly effect in interacting Aubry-Andre model: thermalization, slow scrambling, and many-body localization
    Shenglong Xu, Xiao Li, Yi-Ting Hsu, Brian Swingle, Sankar Das Sarma

    The many-body localization transition in quasiperiodic systems has been extensively studied in recent ultracold atom experiments. At intermediate quasiperiodic potential strength, a surprising Griffiths-like regime with slow dynamics appears in the absence of random disorder and mobility edges. In this work, we study the interacting Aubry-Andre model, a prototype quasiperiodic system, as a function of incommensurate potential strength using a novel dynamical measure, information scrambling, in a large system of 200 lattice sites. Between the thermal phase and the many-body localized phase, we find an intermediate dynamical phase where the butterfly velocity is zero and information spreads in space as a power-law in time. This is in contrast to the ballistic spreading in the thermal phase and logarithmic spreading in the localized phase. We further investigate the entanglement structure of the many-body eigenstates in the intermediate phase and find strong fluctuations in eigenstate entanglement entropy within a given energy window, which is inconsistent with the eigenstate thermalization hypothesis. Machine-learning on the entanglement spectrum also reaches the same conclusion. Our large-scale simulations suggest that the intermediate phase with vanishing butterfly velocity could be responsible for the slow dynamics seen in recent experiments.

  11. Distributional property testing in a quantum world
    András Gilyén, Tongyang Li

    A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. In particular, we give fast quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. The distributions can be either classical or quantum, however our quantum algorithms require coherent quantum access to a process preparing the samples. Our results build on the recent technique of quantum singular value transformation, combined with more standard tricks such as divide-and-conquer. The presented approach is a natural fit for distributional property testing both in the classical and the quantum case, demonstrating the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling; for classical distributions our algorithms significantly improve the precision dependence of some earlier results.

  12. Circuit Transformations for Quantum Architectures
    Andrew M. Childs, Eddie Schoute, Cem M. Unsal
    [Proceedings of TQC 2019]

    Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the routing via matchings framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize routing via matchings to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the token swapping framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.

  13. Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches
    Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang

    Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with m constraint matrices, each of dimension n and rank poly(logn), our algorithm gives a succinct description and any entry of the solution matrix in time O(m⋅poly(log n, 1/ε)) given access to a sample-based low-overhead data structure of the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. 
    Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms.

  14. Quantum spectral methods for differential equations
    Andrew M. Childs, Jin-Peng Liu

    Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(logd). While several of these algorithms approximate the solution to within ϵ with complexity poly(log(1/ϵ)), no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(log d, log(1/ϵ)).

  15. Nearly optimal lattice simulation by product formulas
    Andrew M. Childs, Yuan Su

    Product formulas provide a straightforward yet surprisingly efficient approach to quantum simulation. We show that this algorithm can simulate an n-qubit Hamiltonian with nearest-neighbor interactions evolving for time t using only (nt)^(1+o(1)) gates. While it is reasonable to expect this complexity---in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill---we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.

  16. Efficiently computable bounds for magic state distillation
    Xin Wang, Mark M. Wilde, Yuan Su

    Magic state manipulation is a crucial component in the leading approaches to realizing scalable, fault-tolerant, and universal quantum computation. Related to magic state manipulation is the resource theory of magic states, for which one of the goals is to characterize and quantify quantum "magic." In this paper, we introduce the family of thauma measures to quantify the amount of magic in a quantum state, and we exploit this family of measures to address several open questions in the resource theory of magic states. As a first application, we use the min-thauma to bound the regularized relative entropy of magic. As a consequence of this bound, we find that two classes of states with maximal mana, a previously established magic measure, cannot be interconverted in the asymptotic regime at a rate equal to one. This result resolves a basic question in the resource theory of magic states and reveals a fundamental difference between the resource theory of magic states and other resource theories such as entanglement and coherence. As a second application, we establish the hypothesis testing thauma as an efficiently computable benchmark for the one-shot distillable magic, which in turn leads to a variety of bounds on the rate at which magic can be distilled, as well as on the overhead of magic state distillation. Finally, we prove that the max-thauma can outperform mana in benchmarking the efficiency of magic state distillation.

  17. Bang-bang control as a design principle for classical and quantum optimization algorithms
    Aniruddha Bapat, Stephen Jordan

    Physically motivated classical heuristic optimization algorithms such as simulated annealing (SA) treat the objective function as an energy landscape, and allow walkers to escape local minima. It has been argued that quantum properties such as tunneling may give quantum algorithms advantage in finding ground states of vast, rugged cost landscapes. Indeed, the Quantum Adiabatic Algorithm (QAO) and the recent Quantum Approximate Optimization Algorithm (QAOA) have shown promising results on various problem instances that are considered classically hard. Here, we argue that the type of control strategy used by the optimization algorithm may be crucial to its success. Along with SA, QAO and QAOA, we define a new, bang-bang version of simulated annealing, BBSA, and study the performance of these algorithms on two well-studied problem instances from the literature. Both classically and quantumly, the successful control strategy is found to be bang-bang, exponentially outperforming the quasistatic analogues on the same instances. Lastly, we construct O(1)-depth QAOA protocols for a class of symmetric cost functions, and provide an accompanying physical picture.

  18. Quantum algorithms and lower bounds for convex optimization
    Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Xiaodi Wu
    [Presented at QIP 2019]

    While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using Õ(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization.

  19. Locality and digital quantum simulation of power-law interactions
    Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, Alexey V. Gorshkov
    [To appear in Physical Review X]

  20. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
    András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe
    [Presented at QIP 2019]

    Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new "Singular value transformation" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain "non-commutative" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. "Singular value transformation" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

  21. Quantum algorithms for linear systems of equations inspired by adiabatic quantum computing
    Yigit Subasi, Rolando D. Somma, Davide Orsucci
    [Presented at QIP 2019], [Physical Review Letters]

    We present two quantum algorithms for solving linear systems of equations based on evolution randomization, a simple variant of adiabatic quantum computing. Our algorithms have comparable performance, as a function of the condition number, to existing quantum algorithms for solving linear systems. The algorithms are simple: they are not obtained using equivalences between the gate model and adiabatic quantum computing, they do not use phase estimation, and they do not use variable-time amplitude amplification. Like previous solutions of this problem, our techniques yield an exponential quantum speedup under some assumptions on the linear system being solved. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.

  22. Faster quantum simulation by randomization
    Andrew M. Childs, Aaron Ostrander, Yuan Su

    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.

  23. Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning
    Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, Xiaodi Wu
    [Presented at QIP 2019]

    We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank r, and sparsity s. The first algorithm assumes an input model where one is given access to entries of the matrices at unit cost. We show that it has a run time that gives an optimal dependence in terms of m,n and quadratic improvement over previous quantum algorithms when m≈n. The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its complexity depends only poly-logarithmically in n and polynomially in r. 
    We apply the second SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and copies of an unknown state ρ, we show we can find a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements, up to error ε. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. 
    As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could be of independent interest.