Nearly Optimal Quantum Algorithm for Generating the Ground State of a Free Quantum Field Theory

We devise a quasilinear quantum algorithm for generating an approximation for the ground state of a quantum field theory (QFT). Our quantum algorithm delivers a superquadratic speedup over the state-of-the-art quantum algorithm for ground-state generation, overcomes the ground-state-generation bottleneck of the prior approach and is optimal up to a polylogarithmic factor. Specifically, we establish two quantum algorithms—Fourier-based and wavelet-based—to generate the ground state of a free massive scalar bosonic QFT with gate complexity quasilinear in the number of discretized QFT modes. The Fourier-based algorithm is limited to translationally invariant QFTs. Numerical simulations show that the wavelet-based algorithm successfully yields the ground state for a QFT with broken translational invariance. Furthermore, the cost of preparing particle excitations in the wavelet approach is independent of the energy scale. Our algorithms require a routine for generating one-dimensional Gaussian (1DG) states. We replace the standard method for 1DG-state generation, which requires the quantum computer to perform lots of costly arithmetic, with a novel method based on inequality testing that significantly reduces the need for arithmetic. Our method for 1DG-state generation is generic and could be extended to preparing states whose amplitudes can be computed on the fly by a quantum computer.

Popular Summary

Preparing the ground state of free quantum field theory (QFT) is the most expensive part of current approaches for simulating a bosonic QFT on a quantum computer. We develop two quantum algorithms for preparing the ground state using resources that scale almost linearly with the discretized QFT number of modes. Our algorithms are near optimal, provide more-than-quadratic speedup, and remove ground-state preparation as the most expensive part. For ground-state preparation, we must discretize the QFT and digitize the discretized QFT, both of which introduce errors. We account for these errors in a controlled way and take special care in translating physical inputs for QFT simulation into constructing quantum circuits for state preparation and thoroughly analyzing resource costs.

Our first algorithm is based on the wavelet approach and involves matrix operations. The involved matrices have many zero elements that we exploit to reduce the state-preparation cost. Our second algorithm employs translational invariance of the QFT to eliminate costly matrix operations of prior approaches. The wavelet approach is advantageous for two cases: simulating theories with inhomogeneous mass and preparing excitations above the ground state at variable length scales, which is useful for scattering simulations.

Moreover, we construct two quantum algorithms for preparing one-dimensional Gaussian states, which have applications beyond QFT simulation. Our first algorithm uses a standard state-preparation method, which requires costly arithmetic. We employ novel techniques in our second algorithms to significantly reduce arithmetic operations. Our state-preparation techniques could be used broadly in simulating quantum systems and improving current quantum algorithms for differential equations.

Figure 1

Visual representation of the exact (left) and approximate ICM (right) for the ground state of the discretized free QFT in a multiscale wavelet basis. The column (row) index of the visualized matrix is ordered from left (top) to right (bottom), just as the typical format of a matrix. The values of matrix elements are represented by different colors with the shown color scale. The number of modes for the discretized QFT is $N=2560$, free mass is $m_0=1$, and the Daubechies wavelet with index $\mathcal{K}=3$ is used. The exact ICM is a quasisparse matrix, meaning most of its elements are nearly zero. Elements of the exact matrix with a magnitude less than ${10}^{-8}$ are replaced with zero to obtain the approximate ICM. The approximate ICM has a specific sparsity structure known as the “fingerlike” sparsity structure.

Figure 2

From left to right: scaling $s(x)$ and wavelet $w(x)$ functions for the $\mathrm{db}\mathcal{K}$ wavelet with index $\mathcal{K}=1,2,3$; db1 wavelet is identical to Haar wavelet. The support of these functions is $[0,2\mathcal{K}-1]$. The $s(x)$ and $w(x)$ for db3 wavelet have continuous first derivatives.

Figure 3

Schematic description of the QRAM model. A hybrid code is compiled into the classical processor. The compiled code provides instructions to be performed by classical and quantum processors on their associated registers. The quantum processor sends the measurement results back to the classical processor.

Figure 4

A client-server framework for simulating a QFT. Dashed lines represent classical communication, and solid lines represent quantum communication. The classical inputs to the main and ground-state-generation servers are specified in Tables 1 and 2, respectively, for simulating a massive scalar bosonic QFT. Output from the ground-state-generation server is an approximation for the free-field ground state.

Figure 5

Illustration of state-generation steps before performing an inequality test. First we prepare a state with amplitudes according to the orange points. Then we test an inequality against the blue points. The success probability is at least about $70\mathrm{\%}$.

Figure 6

Description of Fourier-based algorithm for ground-state generation. Top: classical preprocessing. Inputs: wavelet index $\mathcal{K}$, mass $m_0$, number of modes $N$ in the discretized QFT, and error tolerance ${\epsilon }_{\mathrm{vac}}$ for the output state. Each box represents a process; incoming arrows identify the inputs, and outgoing arrows identify the outputs of the process. Outputs: standard deviation $\tilde{\mathit{\sigma }}$ of the approximate one-dimensional Gaussian states and lattice spacing $\delta$. Outputs of intermediate processes: working precision $p$, second-order derivative overlaps $\mathbf{\Delta }$ and eigenvalues $\mathit{\lambda }$ of the ground-state ICM. Bottom: quantum routine. Double lines indicate classical inputs to the quantum routine. vac is a quantum register with $N$ cells, and each cell comprises $p$ qubits; represents multiple qubits. Each oneDG accepts $\delta$ and one component of $\tilde{\mathit{\sigma }}$ as classical inputs and generates an approximate 1DG state corresponding to these inputs on once cell of vac. The quantum fast Fourier transform (qfft) acts collectively on the set of approximate 1DG states and transforms them into the approximate ground state $|\ast ⟩\tilde{G}$.

Figure 7

Description of wavelet-based algorithm for ground-state generation. Top: classical preprocessing. Inputs are the same as the inputs to the Fourier-based algorithm Outputs: shear elements $\mathbf{S}$ of the upper unit-triangular matrix in the UDU decomposition of the approximate ICM, standard deviation $\tilde{\mathit{\sigma }}$ of the approximate one-dimensional Gaussian states and lattice spacing $\delta$. Outputs of intermediate processes: working precision $p$, second-order derivative overlaps $\mathbf{\Delta }$, circulant rows $\mathbf{a}$ of the upper-triangular blocks in the ICM and diagonals $\mathbf{d}$ of the diagonal matrix in the UDU decomposition. Bottom: quantum routine. Double lines indicate classical inputs to the quantum routine. vac is a quantum register with $N$ cells, and each cell comprises $p$ qubits; represents multiple qubits. Each oneDG accepts $\delta$ and one component of $\tilde{\mathit{\sigma }}$ as classical inputs and generates an approximate 1DG state corresponding to these inputs on one cell of vac. The quantum shear transform (qst) acts collectively on the set of approximate 1DG states and transforms them into the approximate ground state $|\tilde{G}⟩$.

Figure 8

Visualization of two $ww$ blocks of the approximate ICM. The left block is a $2$-circulant matrix and the right block is a $4$-circulant matrix. Each $ww$ block has nonzero elements in the top-right, bottom-left, and main part. The parameter $h$ is the NNZ elements in the last column at the top-right part of the block; $W$ is the bandwidth and $H$ is the vertical bandwidth of the block. These parameters specify the location of nonzero entries in the block.

Figure 9

Schematic illustration of our method for storing shear elements in the $ss$ and $ww$ blocks of the upper unit-triangular matrix in the incomplete UDU decomposition of the approximate ICM in a multiscale wavelet basis. To elucidate how we store the shear elements, we use gray color with different scales to show the location of nonzero elements in different parts of a block; gray color’s scale here does not represent the relative magnitude of the elements (a) Visualization of the $ss$ block. This block is an upper unit-triangular matrix. (b) Visualization of the vector storing the $ss$ block’s shear elements. (c) Visualization of a diagonal $ww$ block. This block is also an upper unit-triangular matrix. (d) Visualization of the matrix storing shear elements of the diagonal $ww$ block. (e) Visualization of an off-diagonal $ww$ block. (f) Visualization of the matrix storing the shear elements of the off-diagonal $ww$ block.

Figure 10

Quantum circuit for implementing the iterative steps for 1DG-state generation. Positive integers $p$ and $m$ are, respectively, the total number of bits and position of the radix point in the fixed-point number representation; represents $p$ qubits. $\mathrm{ANGLE}$, Eq. (72), computes a rotation angle, Eq. (71), into the ang register, $\mathrm{ROT}$, Eq. (73), rotates the ${\ell }^{\mathrm{th}}$ qubit of out, $\mathtt{\text{out}}[\ell ]$, by the rotation angle stored in ang and $\mathrm{SHIFT}$, Eq. (74), cyclically shifts qubits of a register one qubit to the right. The Pauli-$X$ gate $X_i^b$ acts on $i^{\mathrm{th}}$ qubit of a register if the binary $b$ is 1. Intermediate results are uncomputed by running the appropriate operations in reverse order.

Figure 11

The success probability for preparing a 1DG state by inequality testing for a wide range of standard deviation and number of qubits $m$; see Eq. (76). The success probability is at least about $70\mathrm{\%}$.

Figure 12

Schematic description of our quantum fast Hartley-transform algorithm for $N=8$; see Eq. (92). Here vac is a quantum register with eight cells, and each cell comprises $p$ qubits encoding a $p$-bit number. qrev, Eq. (96), reorders the values encoded in the input state-vector by swapping qubits of $\mathtt{\text{vac}}[i]$ and $\mathtt{\text{vac}}[\mathrm{rev}(i)]$, where $\mathrm{rev}(i)$ is an integer obtained from $i$ by reversing its binary digits. The algorithm has ${\log }_2N$ stages after qrev, each of which comprises $N/2$ qbf, Eq. (99), operations represented by crossed lines; there are $N/2^s$ blocks of qbf operations at stage $s\in \{1,\dots ,{\log }_2N\}$ and each block comprises $2^s/2$ qbf. qhs performs the Hartley-shift operation on its input state vector as per Eq. (97).

Figure 13

Implementation of rot, Eq. (73), and shift, Eq. (74), by primitive operations. Left: implementing rot using bits of a $p$-bit number $b$ requires at most $p$ standard rotations $R_{\ell }:=\exp (-2\pi \mathrm{i}/2^{\ell })$. Right: implementing shift requires $p$ swap gates.

Figure 14

Effect of a mass defect on the ground-state ICM, Eq. (32), represented in a multiscale wavelet basis. Left: visual representation for approximation of the modified ICM, Eq. (50), in a multiscale wavelet basis where elements with a magnitude less than ${10}^{-8}$ are replaced with exactly zero; rows and columns of the matrix are ordered as the matrix in Fig. 1. Right: bandwidth for diagonal blocks of the approximate ICM with mass defect (orange dashed line) and without mass defect (blue line) for a wide range of mass: $m_0\in [{10}^{-6},{10}^6]$.

Figure 15

From left to right: visualization of the $d$-level wavelet-transform matrix (WTM) with level $d\in \{1,2,3\}$ at scale $k=6$ for the Daubechies wavelet with index $\mathcal{K}=3$; size of matrix is $2^k\times 2^k$. The number of nonzero elements in each row of the one-level WTM is $2\mathcal{K}$. The NNZ elements in those rows of the two-level WTM that pertain to the first level, i.e., the bottom half rows, is $2\mathcal{K}$, and the NNZ elements in the rows pertaining to the second level, the top half rows, is $4\mathcal{K}$. For the three-level wavelet transform, the NNZ elements in those rows pertaining to the third level is 2 times the NNZ elements in the rows pertaining to the second level, which itself is two times the NNZ on the rows pertaining to the first level. The NNZ elements increases by a factor of 2 when we increase the level of wavelet transform by one.

Figure 16

Fourier-based algorithm for ground-state generation

Figure 17

Wavelet-based algorithm for ground-state generation

Figure 18

Classical algorithm for computing eigenvalues of ground-state ICM

Figure 19

Classical algorithm for computing circulant row in blocks of the ICM, Eq. (32), in multiscale wavelet basis

Figure 20

Classical algorithm for UDU decomposition of the approximate ICM in multiscale wavelet basis

Figure 21

Quantum algorithm for generating a one-dimensional Gaussian state

Figure 22

Quantum algorithm for generating a one-dimensional Gaussian state by inequality testing

Figure 23

Quantum fast Hartley transform

Figure 24

Quantum algorithm for a shear transform

Figure 25

Classical algorithm for computing the low-pass filter for Daubechies wavelets

Figure 26

Classical algorithm for computing the second-order derivative overlaps in Eq. (13)

Figure 27

Classical algorithm for UDU decomposition of a dense real-symmetric matrix

Figure 28

Helper functions for location of nonzero elements in blocks of the approximate ICM in multiscale wavelet basis

Figure 29

Helper functions for storing shear elements of the upper unit-triangular matrix in UDU decomposition

Figure 30

Helper functions for computing shear elements

Figure 31

Helper function for 1DG-state generation in Algorithm 21

Figure 32

Helper functions for 1DG-state generation in Algorithm 22

Figure 33

Helper functions for quantum fast Hartley transform in Algorithm 23

Figure 34

Helper functions for quantum shear transform in Algorithm 24