The propagation of information in non-relativistic quantum systems obeys a speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound for systems with interactions that decay with distance r as a power law, 1/rα. The bound implies an effective light cone tighter than all previous bounds. Our approach is based on a technique for approximating the time evolution of a system, which was first introduced as part of a quantum simulation algorithm by Haah et al. [arXiv:1801.03922]. To bound the error of the approximation, we use a known Lieb-Robinson bound that is weaker than the bound we establish. This result brings the analysis full circle, suggesting a deep connection between Lieb-Robinson bounds and digital quantum simulation. In addition to the new Lieb-Robinson bound, our analysis also gives an error bound for the Haah et al. quantum simulation algorithm when used to simulate power-law decaying interactions. In particular, we show that the gate count of the algorithm scales with the system size better than existing algorithms when α>3D (where D is the number of dimensions).

1 aTran, Minh, Cong1 aGuo, Andrew, Y.1 aSu, Yuan1 aGarrison, James, R.1 aEldredge, Zachary1 aFoss-Feig, Michael1 aChilds, Andrew, M.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1808.0522501443nas a2200109 4500008004100000245005800041210005800099520110300157100002301260700001301283856003701296 2019 eng d00aNearly optimal lattice simulation by product formulas0 aNearly optimal lattice simulation by product formulas3 aProduct 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.

1 aChilds, Andrew, M.1 aSu, Yuan uhttps://arxiv.org/abs/1901.0056401870nas a2200133 4500008004100000245004600041210004600087260001500133520150400148100001401652700002001666700001301686856003701699 2019 eng d00aQuantifying the magic of quantum channels0 aQuantifying the magic of quantum channels c2019/03/113 aTo 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.

1 aWang, Xin1 aWilde, Mark, M.1 aSu, Yuan uhttps://arxiv.org/abs/1903.0448301651nas a2200157 4500008004100000245006300041210006100104260001500165520118500180100002301365700002301388700001301411700001401424700001801438856003701456 2019 eng d00aTime-dependent Hamiltonian simulation with L1-norm scaling0 aTimedependent Hamiltonian simulation with L1norm scaling c06/17/20193 aThe 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.

1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aSu, Yuan1 aWang, Xin1 aWiebe, Nathan uhttps://arxiv.org/abs/1906.0711501328nas a2200133 4500008004100000245006600041210006200107260001500169520092300184100001801107700001301125700001901138856003701157 2018 eng d00aApproximate Quantum Fourier Transform with O(nlog(n)) T gates0 aApproximate Quantum Fourier Transform with Onlogn T gates c2018/03/133 aThe ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer enables the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, and phase estimation. The standard fault-tolerant implementation of an n-qubit QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+t gates, incurring the t-count complexity of O(n log2 (n)). In this paper we show how to obtain approximate QFT with the t-count of O(n log(n)). Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

1 aNam, Yunseong1 aSu, Yuan1 aMaslov, Dmitri uhttps://arxiv.org/abs/1803.0493301295nas a2200169 4500008004100000245008000041210006900121260001500190490000600205520078500211100001800996700001901014700001301033700002301046700001901069856003701088 2018 eng d00aAutomated optimization of large quantum circuits with continuous parameters0 aAutomated optimization of large quantum circuits with continuous c2017/10/190 v43 aWe develop and implement automated methods for optimizing quantum circuits of the size and type expected in quantum computations that outperform classical computers. We show how to handle continuous gate parameters and report a collection of fast algorithms capable of optimizing large-scale quantum circuits. For the suite of benchmarks considered, we obtain substantial reductions in gate counts. In particular, we provide better optimization in significantly less time than previous approaches, while making minimal structural changes so as to preserve the basic layout of the underlying quantum algorithms. Our results help bridge the gap between the computations that can be run on existing hardware and those that are expected to outperform classical computers.

1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan1 aChilds, Andrew, M.1 aMaslov, Dmitri uhttps://arxiv.org/abs/1710.0734501848nas a2200121 4500008004100000245006300041210006300104520147500167100001401642700002001656700001301676856003701689 2018 eng d00aEfficiently computable bounds for magic state distillation0 aEfficiently computable bounds for magic state distillation3 aMagic 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.

1 aWang, Xin1 aWilde, Mark, M.1 aSu, Yuan uhttps://arxiv.org/abs/1812.1014501266nas a2200133 4500008004100000245004700041210004700088260001500135520088800150100002301038700002101061700001301082856003701095 2018 eng d00aFaster quantum simulation by randomization0 aFaster quantum simulation by randomization c2018/05/223 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.0838502563nas a2200145 4500008004100000245011000041210006900151260001500220520207500235100001902310700001302329700002002342700001802362856003702380 2018 eng d00aQuantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics0 aQuantum singular value transformation and beyond exponential imp c2018/06/053 aQuantum 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.

1 aGilyen, Andras1 aSu, Yuan1 aLow, Guang, Hao1 aWiebe, Nathan uhttps://arxiv.org/abs/1806.0183801404nas a2200133 4500008004100000245005700041210005500098260001500153490000600168520102800174100001301202700001801215856003701233 2018 eng d00aTime-reversal of rank-one quantum strategy functions0 aTimereversal of rankone quantum strategy functions c2018/01/250 v23 aThe quantum strategy (or quantum combs) framework is a useful tool for reasoning about interactions among entities that process and exchange quantum information over the course of multiple turns. We prove a time-reversal property for a class of linear functions, defined on quantum strategy representations within this framework, that corresponds to the set of rank-one positive semidefinite operators on a certain space. This time-reversal property states that the maximum value obtained by such a function over all valid quantum strategies is also obtained when the direction of time for the function is reversed, despite the fact that the strategies themselves are generally not time reversible. An application of this fact is an alternative proof of a known relationship between the conditional min- and max-entropy of bipartite quantum states, along with generalizations of this relationship.

1 aSu, Yuan1 aWatrous, John uhttps://arxiv.org/abs/1801.0849101648nas a2200169 4500008004100000245006100041210006100102300001400163490000900177520116300186100002301349700001901372700001801391700001901409700001301428856003701441 2018 eng d00aToward the first quantum simulation with quantum speedup0 aToward the first quantum simulation with quantum speedup a9456-94610 v115 3 aWith quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

1 aChilds, Andrew, M.1 aMaslov, Dmitri1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan uhttps://arxiv.org/abs/1711.1098001360nas a2200181 4500008004100000022001400041245007000055210006900125260001500194520081800209100001801027700001901045700001801064700001301082700001901095700001601114856004801130 2017 eng d a1871-409900aExtreme learning machines for regression based on V-matrix method0 aExtreme learning machines for regression based on Vmatrix method c2017/06/103 aThis paper studies the joint effect of V-matrix, a recently proposed framework for statistical inferences, and extreme learning machine (ELM) on regression problems. First of all, a novel algorithm is proposed to efficiently evaluate the V-matrix. Secondly, a novel weighted ELM algorithm called V-ELM is proposed based on the explicit kernel mapping of ELM and the V-matrix method. Though V-matrix method could capture the geometrical structure of training data, it tends to assign a higher weight to instance with smaller input value. In order to avoid this bias, a novel method called VI-ELM is proposed by minimizing both the regression error and the V-matrix weighted error simultaneously. Finally, experiment results on 12 real world benchmark datasets show the effectiveness of our proposed methods.

1 aYang, Zhiyong1 aZhang, Taohong1 aLu, Jingcheng1 aSu, Yuan1 aZhang, Dezheng1 aDuan, Yaowu uhttp://dx.doi.org/10.1007/s11571-017-9444-2