A simple quantum simulation algorithm with near-optimal precision scaling
Amir Kalev, Itay Hen · 2024
Read A simple quantum simulation algorithm with near-optimal precision scaling by Amir Kalev, Itay Hen (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10667.txt.
Introduction
Amir Kalev and Itay Hen propose a simple quantum simulation algorithm with near-optimal scaling in precision, in work from 2024. Quantum simulation is a core promise of quantum computers, since it can probe systems beyond classical reach. Most known methods, apart from Trotter-based ones, are intricate to run on early fault-tolerant hardware, while Trotter methods scale poorly with precision.
Catalog record
| CREATOR | Amir Kalev, Itay Hen |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-10667
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A simple quantum simulation algorithm with near-optimal precision scaling Amir Kalev, Itay Hen Abstract Quantum simulation is a foundational application for quantum computers, projected to offer insights into complex quantum systems beyond the reach of classical computation. However, with the exception of Trotter-based methods, which suffer from suboptimal scaling with respect to simulation precision, existing simulation techniques are, for the most part, too intricate to implement on early fault-tolerant quantum hardware. We propose a quantum Hamiltonian dynamics simulation algorithm that aims to be both straightforward to implement and, at the same time, have near-optimal scaling in simulation precision. I Introduction Quantum computers are widely believed to have unique advantages over classical computers when it comes to simulating Hamiltonian dynamics, due to their inherent quantum nature, which allows them to efficiently represent complex quantum states and the evolution thereof. Such simulations hold the potential to solve intricate problems in quantum chemistry, materials science, and physics, making quantum computers potentially very powerful future tools for advancing scientific knowledge and tackling challenges beyond the capabilities of classical computing. The precise manner in which Hamiltonian dynamics can be approximated on quantum devices varies considerably between approaches, as each is tailored to different resource constraints, runtime requirements, and precision needs. Perhaps the most straightforward and resource-efficient technique is that of Trotterization, in which case the time-evolution operator is approximated using Trotter-Suzuki product formulas [ Lloyd:96 , PhysRevX.11.011020 ] . This approach is simple to implement; however, it suffers from a suboptimal scaling of the resources required for its execution with error tolerance. A more advanced and vastly popular technique is quantum signal processing (QSP) [ QSP ] , which leverages a sequence of unitary operations combined with classical preprocessing to directly approximate the exponential of a Hamiltonian. Complementing QSP, the linear combination of unitaries (LCU) framework [ Berry1 ] encompasses some of the most powerful quantum simulation methods [ Berry1 , Kalev2021quantumalgorithm , PRXQuantum.2.030342 , PhysRevLett.131.150603 , Chakraborty2024implementingany ] . In LCU-based approaches, the time evolution operator is expressed as a linear combination of efficiently implementable unitary operators, with ancillary qubits facilitating the simulation through oblivious amplitude amplification [ OAA ] . This method is particularly advantageous for simulating Hamiltonians in quantum chemistry and materials science, where the decomposition of the Hamiltonian into simpler components is feasible. Despite enjoying near-optimal scaling of resources with respect to target precision — typically requiring only a logarithmic number of ancillary qubits — these more advanced approaches present significant challenges for implementation on near-term quantum computing devices. For example, in the typical LCU-based approach, the ‘select’ unitary transformations are (multi-qubit) control of Pauli strings. These control operations, which involve different Pauli operations acting on different qubits, translate to a non-trivial overhead in resources, which then hinders the technique’s otherwise straightforward applicability on near-term quantum computing devices. In this work, we present a novel LCU-based quantum simulation algorithm designed to be both straightforward to implement, by generally requiring only control-not (CNOT) operations as the select unitaries, while at the same time offering the benefits of near-optimal resource scaling, making dynamical simulations potentially more accessible for near-term devices. The simulation algorithm we present here builds on two recent studies [ Kalev2021quantumalgorithm , PRXQuantum.2.030342 ] that have shown how the expansion of the unitary time-evolution operator in powers of its off-diagonal strength [ ODE , ODE2 , pmr ] combined with the use of the concept of divided differences [ dd:67 , deboor:05 ] leads to resource-efficient quantum simulation algorithms whose complexity is on par and, in some cases, superior to other state-of-the-art optimal-precision simulation protocols [ Berry1 , 2018arXiv180500675H ] . The approach we present here, which we refer to as the permutation matrix representation (PMR) simulation method, similarly utilizes a series expansion of the quantum time-evolution operator in its off-diagonal elements. However, in contrast to the work depicted in Refs. [ Kalev2021quantumalgorithm , PRXQuantum.2.030342 ] , here we utilize a powerful approximation of divided differences which allows us to render those in terms of sums of phases, which in turn leads to simplifications in the select unitary operations. As we demonstrate, when the above approximation is combined with the LCU technique, the resulting simulation algorithm enjoys both near-optimal scaling in terms of the overall simulation error and simple-to-implement CNOTs interleaved with controlled phases as the select unitary operations. The paper is organized as follows. In Sec. II , we provide an overview of the permutation matrix representation technique, which serves as a foundation for our algorithm. In Sec. III , we present the Hamiltonian dynamics algorithm, which we construct using PMR, and discuss the divided difference calculation including cost analysis and various extensions. In Sec. we demonstrate the scaling advantages of our method by analyzing in detail the algorithm as it is applied to two specific models, namely the Rydberg atom Hamiltonian and dipolar molecules in optical lattices. A discussion and some conclusions are given in Sec. . II Permutation matrix representation of the time evolution operator Before delving into the technical specifics of our algorithm, we first briefly present the key components of the PMR approach, which we use to expand matrix exponentials in a series [ pmr , Kalev2021quantumalgorithm , PRXQuantum.2.030342 ] . For concreteness, we restrict our attention here to time-independent Hamiltonians and defer the discussion of how the method can be extended to the time-dependent case to the concluding section. The PMR expansion consists of several steps, the first of which is choosing a preferred basis, the ‘computational basis’, in which the Hamiltonian matrix is represented, and casting the Hamiltonian H as a sum of a diagonal operator and an off-diagonal operator in that basis. Hereafter, we denote the set of computational basis states as \{|z\rangle\} . Intuitively, the diagonal part of the Hamiltonian corresponds to a ‘classical’ Hamiltonian, whereas its off-diagonal part governs the non-trivial ‘quantum’ dynamics of the system in the chosen basis. The off-diagonal component is further decomposed to a sum of products of diagonal and permutation operators [ pmr ] . This defines the PMR form of the Hamiltonian: H=D_{0}+\sum_{i=1}^{M}D_{i}P_{i}\,, (1) where the D_{i} ’s are diagonal operators and the P_{i} ’s are permutation operators, i.e., operators that permute the basis states. For example, for qubit systems, if one chooses the computational basis to be the eigenbasis of the Pauli- Z operators, then the P_{i} operators are strings of Pauli- X operators. The decomposition Eq. ( 1 ) can be carried out efficiently for any physical Hamiltonian [ pmr ] . Next, consider the evolution of a quantum state under H for duration t , which is then split to a sequence of r repeated short-time evolution operators, each evolving the state by a short time period \Delta t=t/r , the value of which we determine later on in a manner designed to optimize resources (we discuss this in detail in Sec. ). The PMR decomposition of the Hamiltonian allows us to write the (short) time evolution operator U(\Delta t)=e^{-iH\Delta t} in an off-diagonal series expansion: \displaystyle e^{-iH\Delta t} \displaystyle=\sum_{n=0}^{\infty}\frac{(-i\Delta t)^{n}}{n!}H^{n}=\sum_{n=0}^{\infty}\frac{(-i\Delta t)^{n}}{n!}\Big(\sum_{i=0}^{M}D_{i}P_{i}\Big)^{n}, (2) where in the last step we identify P_{0} with the identity operator. After some algebra, this expansion (see Refs. [ ODE , pmr ] for a complete and detailed