Digital-analog quantum algorithm for the quantum Fourier transform

PHYSICAL REVIEW RESEARCH 2, 013012 (2020) Digital-analog quantum algorithm for the quantum Fourier transform Ana Martin,1,*Lucas Lamata,1,2Enrique Solano,1,3,4and Mikel Sanz 1,† 1Department of Physical Chemistry, University of the Basque Country, Apartado 644, 48080 Bilbao, Spain 2Departamento de Física Atómica, Molecular y Nuclear, Universidad de Sevilla, 41080 Sevilla, Spain 3IKERBASQUE, Basque Foundation for Science, Maria Diaz de Haro 3, 48013 Bilbao, Spain 4International Center of Quantum Artificial Intelligence for Science and Technology (QuArtist) and Department of Physics, Shanghai University, 200444 Shanghai, China (Received 21 June 2019; published 6 January 2020) Quantum computers will allow calculations beyond existing classical computers. However, current technology is still too noisy and imperfect to construct a universal digital quantum computer with quantum error correction. Inspired by the evolution of classical computation, an alternative paradigm merging the flexibility of digital quantum computation with the robustness of analog quantum simulation has emerged. This universal paradigm is known as digital-analog quantum computing. Here, we introduce an efficient digital-analog quantum algorithm to compute the quantum Fourier transform, a subroutine widely employed in several relevant quantum algorithms. We show that, under reasonable assumptions about noise models, the fidelity of the quantum Fourier transformation improves considerably using this approach when the number of qubits involved grows. This suggests that, in the noisy intermediate-scale quantum era, hybrid protocols combining digital and analog quantum computing could be a sensible approach to reach useful quantum supremacy. DOI: 10.1103/PhysRevResearch.2.013012 I. INTRODUCTION Almost four decades ago, a new paradigm, based on laws of quantum mechanics, had been put forward by Manin [1] and Feynman [2]. The new paradigm employed quantum features to speed up calculations, and it was called quantum simulation or quantum computation (QC). There exist several computational tasks for which QC offers exponential speedups over their classical counterparts [3,4]. If we had a fully functional error corrected quantum computer, we would be able to solve problems that not even the largest classical supercomputers can. But, nowadays, we are far from this point. The first series of commercial digital quantum processors based on superconducting circuits have been introduced by companies, such as IBM, Rigetti, Google, and Alibaba. These devices belong to the so-called noisy intermediatescale quantum (NISQ) era in which their performance still faces multiple technical constraints. These constraints pose a great challenge when one tries to solve real-world problems, limiting its size to the small scale [5,6]. Quantum error mitigation (QEM) techniques have been proposed as a possible method to bypass the NISQ- era hardware limitations and improve the calculation of mean values of observables in problems comprising short- *Corresponding author: [email protected] †Corresponding author: [email protected] Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI. depth circuits [7]. These techniques, in general, postprocess the information in order to mitigate the effects of the noise [8–11]. Parra-Rodriguez et al. introduced, in Ref. [12], an alternative hybrid quantum computation approach which could reduce the limitations of NISQ devices. This universal paradigm, called digital-analog quantum computation (DAQC), merges the flexibility of digital quantum computation with the robustness of analog quantum simulators. If our analog resource is the natural interaction Hamiltonian in the platform, then applying fast single-qubit rotations in certain order, one can generate an arbitrary Hamiltonian. They claim that this codification is susceptible to smaller errors than digital quantum computing when performing quantum simulations. It is noteworthy to mention that, even though the Hamiltonian employed is the Ising model, the DAQC approach is universal with essentially every Hamiltonian [13]. A natural question is whether quantum algorithms with possible speedup can be efficiently written using this paradigm. The quantum Fourier transform (QFT) is a key ingredient for several quantum algorithms, such as Shor’s algorithm for factorization [3] or the quantum phase estimation algorithm for the estimation of the eigenvalues of a unitary operator [14]. The latter additionally appears as a subroutine of other algorithms, such as the Harrow-Hassidim- Lloyd (HHL) algorithm for linear systems of equations [15] or the quantum principal component analysis algorithm [16]. The quantum version of the discrete Fourier transform (DFT) has an exponential speedup over its classical counterpart. Although, on the classical version, it is necessary to apply O(n2n) gates, where nrefers to the number of bits, on the quantum approach only O(n2) gates are needed, in this case n stands for the number of qubits. 2643-1564/2020/2(1)/013012(9) 013012-1 Published by the American Physical Society MARTIN, LAMATA, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 013012 (2020) In this article, we show how to efficiently write the QFT algorithm using the DAQC paradigm and demonstrate that it achieves better results than the purely digital approach on a noisy hardware. For that purpose, we considered the homogeneous all-to-all (ATA) two-body Ising model as a resource for DAQC implementation, and we express the Hamiltonian of the QFT as an inhomogeneous ATA two-body Ising model. Afterwards, we simulate numerically the cases of a three-, five-, six-, and seven-qubit device, introducing reasonable noise models in the interactions. Additionally, we have performed the QFT of a certain family of states using both the purely digital and the DAQC approaches. The fidelity between the ideal transformation and the one achieved by the DAQC behaves qualitatively better with the number of qubits than the fidelity offered by the digital implementation. Although this new paradigm has its own noise sources, it eliminates the errors derived from the entangling two-qubit gates. Getting rid of these sources of errors allows us to successfully implement relevant quantum algorithms in the NISQ era. II. DIGITAL-ANALOG QUANTUM COMPUTING There are two main approaches to implement QC, namely, the digital quantum computation (DQC) and the analog quantum simulation. A digital quantum computer, which is based on quantum circuits and the quantum gate model, is a physical platform, such as trapped ions [17,18] or superconducting circuits [19–24], which can be programed to efficiently simulate another dynamics of interest. The drawback of this approach is that it consumes too many resources to implement useful applications beyond desired computation so that it can hardly be considered a viable option with current technology. Some examples of this approach are in the simulation of quantum machine learning [25,26], finance [6,27], open quantum systems [28], quantum chemistry [29], or quantum field theories [22], among others. On the other hand, analog quantum computing uses a controllable quantum system whose dynamics is known to mimic the dynamics of another system of interest. There are multiple results following this approach simulating, for instance, the quantum Rabi model [30–34], fluid dynamics [35], or Casimir physics [36–38], among others. Merging these two approaches, leads to a paradigm known as digital-analog quantum computation [12,39–41]. A digitalanalog protocol, built combining analog blocks with digital steps, shows the flexibility of the digital gate model [42] and the robustness of the analog simulation model. A formal definition of these elements could be found in Ref. [12]. Here, we give a practical definition: a digital step is constituted by single-qubit unitary operations, whereas an analog block is constituted by the time evolution of a known interaction Hamiltonian. The most popular quantum processors are based on superconducting circuits where the role of the qubits is played by transmons. The interactions that appear in such physical systems are well described by the inhomogeneous ATA two-body Ising Hamiltonian. Something similar happens with spin-spin interaction in trapped ions. Therefore, from here on, we will use the unitary evolution generated by homogeneous ATA FIG. 1. Comparison between the sDAQC and the bDAQC protocols. The blue blocks Uint(t) represent the analog blocks, and the single-qubit gates Xrefer to the Pauli matrix σx.InthesDAQC protocol, the digital and the analog blocks alternate with each other. The evolution of the interaction Hamiltonian is turned on and off several times. When applying the bDAQC protocol, the analog block is turned on during the whole simulation, and the digital blocks are performed on top of the analog evolution. two-body Ising Hamiltonian as the elementary analog block, H0=Hint =g N  j<k Z(j)Z(k)→Uint(t)=eitHint , where gis a fixed coupling strength and Z(i)is the Pauli matrix σ(i) zapplied on the ith qubit. For the digital steps, we will employ single-qubit unitary rotations around the X axis with continuous angle θbetween 0 and 2πrad. As we will explain below, our goal is to generate an arbitrary ATA inhomogeneous Hamiltonian, HZZ = N  j<k gjkZ(j)Z(k)with UZZ =eitFHZZ .(1) The problem reduces to find an appropriate map between tFgj,kand gtnm by slicing the homogeneous time-evolution Uzz(t)intoN(N−1)/2 analog blocks of different timelengths tnm, sandwiched by the local rotations X(n)X(m)as explained in Ref. [12] and depicted in Fig. 1. This mapping yields HZZ = N  j<k gj,kZ(j)Z(k) =g tF N  j<k N  n<m tnmX(n)X(m)Z(j)Z(k)X(n)X(m).(2) 013012-2 DIGITAL-ANALOG QUANTUM ALGORITHM FOR THE … PHYSICAL REVIEW RESEARCH 2, 013012 (2020) As X(n)Z(k)X(n)is equal to −Z(n)if n=k, and it is equal to Z(k)otherwise, then, HZZ =g tF N  j<k N  n<m tnm(−1)δnj+δnk +δmj+δmk Z(j)Z(k).(3) Thus, the problem of finding the value of each time tnm is a matrix-inversion problem, gβ=tαMαβ g tF→tα=M−1 αβ gβ tF g,(4) where αand βare introduced to vectorize each pair of indices (n,m) and (j,k)as α=N(n−1)−n(n+1) 2+m, β=N(j−1)−j(j+1) 2+k,(5) and Mis a sign matrix built up by the elements, Mαβ =(−1)δnj+δnk +δmj+δmk .(6) This sign matrix Mis a nonsingular matrix ∀N∈Z−{4}. This means that, for the case of N=4 qubits, we need a different set of single-qubit rotations. This case is discussed in detail in Ref. [12]. The method aforementioned is called stepwise DAQC (sDAQC) and, under ideal circumstances, i.e., without taking into account noise sources or experimental errors, would lead to the same state as the DQC method. There is another variant of the DAQC method, called the banged DAQC (bDAQC) protocol. In this case, the analog Hamiltonian is on during the whole simulation, and the single-qubit rotations are preformed on top of it. Note that, in the previous case, the analog evolution is turned off before applying single-qubit rotations. The total amount of time in which the analog block is on in the bDAQC is the sum of the different analog blocks in the sDAQC protocol as shown in Fig. 1. The bDAQC does not generate the same result as the sDAQC or the DQC method. There is an intrinsic error on the bDAQC which does not depend on either the experimental conditions or the noise sources. This error is due to the superposition between the Hamiltonians of the single-qubit rotations and the analog Hamiltonian. However, one could expect that, if single-qubit rotations are performed in a time tmuch smaller than the intrinsic timescale of the analog block, the error will be smaller than the one coming from switching on and off the analog Hamiltonian. Indeed, the additional error per single-qubit rotation introduced by not turning off the evolution of the Hamiltonian is on the order of O[()3][12]. The reason why we aim at using the bDAQC protocol despite its intrinsic error is because it accumulates less experimental error. Experimentally, switching on and off the Hamiltonian is not an exact step function, it takes some time to stabilize. Quantum control tries to suppress these errors, but it turns cumbersome when the system scales up and cannot be solved in a classical computer. If we keep the analog block on during the evolution, we will avoid these errors. This will be of great importance when we explore a more realistic implementation of the DAQC protocol in Sec. IV. FIG. 2. Digital implementation of the QFTforan-qubit system. The single-qubit gate Hcorresponds to the Hadamard gate [see Eq. (9)]. The rest are the controlled rotations defined by cRk=|00|⊗1+|11|⊗Rk,whereRk=|00|+e2πi/2k|11|. The swap gates at the end of the circuit needed to correctly read the transformed state are not shown. III. QUANTUM FOURIER TRANSFORM: DESCRIPTION AND IDEAL CASE IMPLEMENTATION DFT plays an important role in mathematics, engineering, and physics. This mathematical transformation takes a complex vector of length N,(x0,x1,...,xN−1) and transforms it into another complex vector of the same length (y0,y1,...,yn−1) whose kth element is defined as yk≡1 √N N−1  j=0 xje2πij.(7) QFT, its quantum counterpart, is a linear operator Fwith the following action on the basis states: F|≡ 1 √N N−1  k=0 e2πik/N|k,(8) where N=2nand nis the number of qubits of the system. The quantum-circuit implementation of the QFT is depicted in Fig. 2. The only single-qubit gates applied are Hadamard gates H, whose unitary matrix and Hamiltonian expressions are H=eiHH=1 √211 1−1,HH=π 21−1 √2(Z+X), (9) respectively. The entangling two-qubit gates of the circuit implementation are the controlled-Rkoperations with Rk=10 0e2πi/2k,(10) cRk=|00|⊗1+|11|⊗Rk=⎛ ⎜ ⎜ ⎝ 100 0 010 0 001 0 000e2πi/2k ⎞ ⎟ ⎟ ⎠ . (11) They appear in (n−1) different blocks of controlled rotations, all of them preceded by a Hadamard gate as shown in Fig. 2. In order to apply the DAQC protocol to implement the QFT, we express the unitary matrices defined in Eq. (11)in terms of an inhomogeneous ATA two-body Ising Hamiltonian. Indeed, UQFT=n−1  m=1 USQG,mUTQG,mUH,m,(12) 013012-3 MARTIN, LAMATA, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 013012 (2020) where USQG,m=exp i n−(m−1)  k=2 θk(1N×N−Z(k+m−1) −Z(m)) ×exp iπ 21−Z(m)+X(m) √2,(13) UTQG =exp i n  c<k αc,k,mZ(c)⊗Z(k),(14) UH,m=exp iπ 21(m)−(Z(m)+X(m)) √2,(15) θk=π 2k+1and αc,k,m=δc,m π 2k−m+2.(16) The superindices in brackets specify the qubit in which the unitary operation is performed. In Fig. 3, we depict the DQC implementation of the QFT using Eqs. (13)–(15). As one can see, each controlled-rotation block can be implemented by applying first a set of singlequbit gates, and then a set of two-qubit gates. This is why we decompose the complete unitary transformation into three different operations. The subindices SQG and TQG stand for single-qubit gates and two-qubit gates, respectively. Every two-qubit gate is applied following the ATA DQC protocol and using a fixed π/4 phase, eiϕμν jk σj μσk ν=ei(π/4)σj yei(π/4)σj μσk νeiϕμν jk σj ye−i(π/4)σj μσk νe−i(π/4)σj y. (17) In our case, μ=ν=Zand the phase ϕμν jk correspond to the coefficient αc,k,m,giveninEq.(16), eiαc,k,mZcZk=ei(π/4)Ycei(π/4)ZcZkeiαc,k,mYcXk ×ei(π/4)ZcZkXke−i(π/4)Yc.(18) The inhomogeneous ATA two-body Ising Hamiltonian which we want to write in the DAQC framework [see Eq. (14)] represents a complete block of controlled rotations, and it is different for each block. This means that we need to apply the DAQC protocol (n−1) times, one time per controlledrotation block as depicted in Fig. 3. In order to compare each protocol (DQC, sDAQC, and bDAQC), we compute the QFT of the family of states |ψ0= sin β|Wn+cos β|GHZn, where βruns from 0 to πand n refers to the number of qubits of the system. We perform this for a three-, five-, six-, and seven-qubit system to grasp the behavior of the fidelity when the number of qubits scales up. As a figure of merit, we have calculated the fidelity between the states after the exact transformation and the ones obtained by the applied different methods, Fmethod =ψexact Fψmethod F2.(19) The results obtained are depicted in Fig. 4(a). According to the aforementioned arguments, the expected fidelity for both the digital case and the stepwise case is FDQC =FsDAQC =1 since the implementation is exact and ideal. This holds independently of the number of qubits of the system. The fidelity obtained when applying the bDAQC is always FbDAQC <1 due to the intrinsic error associated with this method. The fidelity decreases with the number of qubits, but F3,5–7 bDAQC > 0.90 for n=3,5–7 qubits. IV. REALISTIC IMPLEMENTATION WITH EXPERIMENTAL ERRORS Impurities in the materials comprising superconductive circuits and spurious interactions among superconducting qubits (cross talk) and with two-level fluctuators modify the dynamics of the system, directly affecting the results of an experiment. Additionally, there are relevant control errors in the pulses when applying the gates. In order to make a fair comparison among different methods, we must introduce the effects of errors in the dynamics. In single-qubit gates, we have introduced a magnetic-field noise Bγby adding to the Hamiltonian of the single-qubit gate a random variable taken from a uniform probability distribution centered in 1, i.e., U(1 −SQGN,1+SQGN). We have chosen SQGN =0.0005. For the two-qubit gates, we add a Gaussian phase noise ∈N(0,TQGN) with variance TQGN =0.2000 to the π/4 phases in the DQC protocol. Finally, to model the experimental control error on the analog blocks, we include a Gaussian coherent noise to the time those blocks are applied, this is t→t+δ, where δ∈N(0,ABN). The value of the variance ABN depends on which DAQC protocol we are using. The value used on the sDAQC is double the value used for the bDAQC case. The values we have considered are ABNs=0.0200 for the sDAQC case and ABNb=0.0100 for the bDAQC case. Thus, each ideal gate transforms as eiθkZ→eiθkBZ,(20) ei(π/4)ZZ →ei(π/4)(1+)ZZ,(21) eitαHint →ei(tα+δ)Hint .(22) To test how the fidelity behaves for each case, we have computed the QFT of the family of states |ψ0=sin β|Wn+ cos β|GHZn. We repeated the simulation 1000 times and calculate the average for a three-, five-, six-, and seven-qubit system. Both the sDAQC and the bDAQC perform better than the DQC protocol under realistic conditions as depicted in Fig. 4(b). The best result corresponds to the bDAQC, a completely different situation from the ideal case. The reason is that turning on and off the interaction Hamiltonian is much more prone to suffer from experimental errors than keeping it on until the end of the computation. Note that the fidelity of the DQC decreases faster than the fidelity of the DAQC protocols with the number of qubits of the system. An extrapolation of these results to larger systems might indicate the convenience of this paradigm to foster near-term quantum computation. This shows the convenience of this paradigm to foster near-term quantum computation. The reason why the fidelity in Fig. 4(b) decays so fast with the number of qubits Nis the quadratic increment O(N2) in the depth of the algorithm. This is an exponential speedup with respect to the classical algorithm, but the errors accumulate very fast with the system size. As a consequence, the implementation of the QFT, which is a key subroutine in many other quantum algorithms, is a challenge when compared against algorithms with logarithmic scaling. This shows the importance of exploring alternative approaches, such as our DAQC, to optimize the implementation of this quantum algorithm. 013012-4 DIGITAL-ANALOG QUANTUM ALGORITHM FOR THE … PHYSICAL REVIEW RESEARCH 2, 013012 (2020) FIG. 3. Implementation of the QFT for a three-qubit system using three different protocols: DQC, sDAQC, and bDAQC. Digital implementation: We show the transformation between the usual DQC implementation of the QFT (see Fig. 2) and the one that follows the Hamiltonian described by Eq. (14). Following Eq. (11), the controlled-rotation cR2and cR3correspond to the controlled-phase gate cS and the controlled-π/8gatecT , respectively. For the implementation that follows the Hamiltonian described by Eq. (14), each entangling two-qubit gate is applied according to the ATA DQC protocol using a fixed π/4 phase [see Eq. (18)]. DAQC implementation: The blue blocks Uint(t) represent the analog blocks, and each of them is applied during different times t. The single-qubit gates Xrefer to the Pauli matrix σxand act for a time t. We apply the DAQC protocol for each block of controlled rotations of the DQC implementation, which is detailed by the red line over each of those blocks. The sDAQC switches on and off the analog evolution before applying the single-qubit rotations X. In contrast, in the bDAQC protocol, the single-qubit rotations are performed on top of the analog evolution. Since we are applying a Suzuki-Lie-Trotter decomposition to minimize the error, between the single-qubit rotations, each analog block acts for different times ti−t, except for the first and the last block, which act for times ti−3 2t. Additionally, we have studied how the fidelity behaves with different values for the errors. We have computed the QFTof state |ψ0=sin π 4|Wn+cos π 4|GHZnfor n=3,5–7 qubits employing the three protocols. Again, the fidelity obtained when we use the bDAQC protocol behaves better than the one obtained by using the DQC protocol. For the three-qubit case, the fidelity is higher than 99%, for five qubits, it stays above 85%, and for six qubits, it is greater than 70%. For seven qubits, we obtain significantly lower fidelity than in the previous systems for the three protocols, but the one offered by the bDAQC remains above those offered by the DQC and the sDAQC. These results are depicted in Fig. 4(c). Similar 013012-5 MARTIN, LAMATA, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 013012 (2020) FIG. 4. Fidelity of the transformation of the family of states |ψ0=sin β|Wn+cos β|GHZnusing the three protocols. (a) Ideal implementation. Both the DQC and the sDAQC protocols perform the QFT with fidelity FDQC =FsDAQC =1. The bDAQC has an intrinsic error due to the fact that the analog block is applied during the whole process. In this case, the fidelity is FbDAQC ∈(0.90,1). (b) Realistic noisy implementation. In this situation, the intrinsic error of the bDAQC is less significant than the experimental errors of the DQC and the sDAQC. The fidelity of the DQC decreases fast with the number of qubits. For a six-qubit system, the fidelity is around 50%, so the DQC protocol is no longer useful. The fidelity of both DAQC protocols behaves better than the one of the DQC with the number of qubits and remains above 70% for the sDAQC and over 80% for the bDAQC. For the case of a seven-qubit system, we obtain a similar fidelity for both the DQC and the sDAQC protocols, but the one obtained for the bDAQC remains remarkably higher. This shows that the bDAQC protocol is the best option if one wants to implement the QFT on a system built up from several qubits. (c) Fidelity evolution with growing errors. We want to show how the fidelity behaves if the errors we have estimated are slightly different. We have computed the QFT of state |ψ0=sin π 4|Wn+cos π 4|GHZn for a system of three, five, six, and seven qubits. The fidelity of the two DAQC protocols is better than the fidelity obtained with the DQC, no matter what the errors are. Note that, in the DQC protocol, the error of the two-qubit gates dominates in the total error. Similarly, the fidelity in the DAQC is mainly affected by the errors in the analog blocks, to the DQC case in which the error of the two-qubit gates dominates in the total error, the fidelity in the DAQC is mainly affected by the errors in the analog blocks. The results of the simulations shown in Fig. 4should not be understood as the expected fidelity arising from an experiment since it will strongly depend on the fabrication, architecture, and materials, among other factors. The actual result is that the distance between the fidelities of the bDAQC and the DQC are always remarkable in favor of the bDAQC. Even though we have considered a sensible choice for the noise model of the DAQC implementation, this model will not be accurate until comparing it against experimental data. We would like to point out that, although the connectivity of most quantum systems is not ATA, with the remarkable exception of trapped ions and NMR, we have chosen it for the sake of simplicity. It can be shown that, using the DAQC paradigm, one can simulate a N-qubit ATA Ising Hamiltonian making use of, at most, 1 2N(N−1) nearest-neighbor (NN) Hamiltonians. This quadratic overhead holds in the worst-case scenario, but it can be substantially reduced if there exists some pattern in our couplings (see the Appendix). However, this overhead (or worse) also holds for the DQC paradigm. Consequently, the values of the fidelities could change in the case of considering NN Hamiltonians, but the comparison shown between DQC and DAQC is fair, and the conclusion related to the better performance of the bDAQC with respect to the DQC still holds. V. CONCLUSIONS AND PERSPECTIVES We have shown that the DAQC paradigm can enhance the depth of the implementation of a quantum algorithm. In particular, we have provided a digital-analog algorithm for the QFT, a ubiquitous quantum subroutine, which is a relevant part of several quantum algorithms. Improving the fidelity of the implementation of QFT, consequently, enhances applicability of other quantum algorithms, such as Shor’s algorithm for prime number factorization or the HHL algorithm for solving linear systems of equations. The main problem of the digital approach for the QFTin a real NISQ chip is that its fidelity decays fast when scaling up since the depth of the algorithm grows quadratically with 013012-6 DIGITAL-ANALOG QUANTUM ALGORITHM FOR THE … PHYSICAL REVIEW RESEARCH 2, 013012 (2020) the number of qubits. Although there exist QEM techniques to reduce the DQC implementations, they are restricted to shortdepth quantum algorithms, which constrains the achievable quantum volume of the algorithms, consequently restricting the original problem to a size in which DQC offers a reliable fidelity. In this paper, we have shown that DAQC could allow us to attain larger algorithm volumes, whereas keeping the fidelity under control. Indeed, we have simulated the QFT for three, five, six, and seven qubits, keeping the fidelity of the algorithm above 80%. In a similar situation, the fidelity provided by the DQC protocol is between 50% and 65%. As a future work, it would be useful to include other types of errors, such as decoherence, and study the behavior of the fidelity with these errors. Taking into account the advantages that the DAQC paradigm offers, the next step is to study the implementation of quantum algorithms comprising the QFT as a subroutine. Additionally, it would also be interesting to implement other quantum algorithms, such as Grover’s algorithm. The successful implementation of these algorithms would pave the way for achieving useful quantum supremacy in the NISQ era. ACKNOWLEDGMENTS The authors acknowledge support from Spanish Government PGC2018-095113-B-I00 (MCIU/AEI/FEDER, UE) and Basque Government IT986-16. The authors also acknowledge support from the projects QMiCS (820505) and OpenSuperQ (820363) of the EU Flagship on Quantum Technologies, as well as EU FET Open Grant Quromorphic (828826). This material is also based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advance Scientific Computing Research (ASCR), under field work proposal number ERKJ333. APPENDIX: ENHANCING CONNECTIVITY IN QUANTUM PROCESSORS The connectivity of many quantum systems is not ATA as assumed in this paper. For the aim of this paper, this is not important since we are trying to compare the performance of the DAQC approach against the DQC one, and we are assuming ATA gates for the DQC. The choice of the ATA connectivity in this paper is, therefore, made for the sake of simplicity since it can be shown [43] that, using the DAQC paradigm, one can simulate a L-qubit ATA Ising Hamiltonian making use of, at most, L(L−1)/2 NN Hamiltonians. Indeed, the quadratic overhead holds in the worst-case scenario, but it can be substantially reduced if there exists any pattern in the couplings [43]. Consequently, this transformation from the NN to ATA layout is physically equivalent to enhance the connectivity of the chip in the software level without changing the architecture of the hardware or employing ancillary qubits. In the following, we present a brief description on how to proceed to attain this transformation. For a more detailed explanation, see Ref. [43]. We can understand the Ising Hamiltonian for Lqubits as a weighted graph of Lvertices where the weight of the edge that connects the vertex ito the vertex jis the coupling constant gij. If two vertices iand jare not connected, then gij =0. Using this interpretation, an ATA Ising Hamiltonian of Lqubits corresponds to a complete graph KL, which is a graph with edges among every possible vertex with no repetition. The NN Ising Hamiltonian is then represented as a path that visits all the possible vertices only once. This is called the Hamiltonian path (HP). The problem reduces to the decomposition of a KLgraph into a set of HPs using a NN Hamiltonian as a resource. For simplicity, we will assume that we are dealing with unweighted graphs, which are equivalent to homogeneous Ising Hamiltonians. To obtain an efficient decomposition, we require a set of at most L(L−1)/2 HPs. This set of kHPs is generated by a vertex permutation P, given by Pk L(j)=k−1+j 2mod L+1,if jeven, k−1−j−1 2mod L+1,if jodd,(A1) with Las the number of qubits, k∈Zsuch that 0 ⩽k⩽L/2, and jrepresents the jth position of the vertex permutation. We will obtain each HP employing a NN Hamiltonian as a resource. For this, we will change the connection of the resource using an ISWAP gate, which performs the following operations: U(Z⊗1)U†=1⊗Z, U(1⊗Z)U†=Z⊗1.(A2) The ISWAP gate Uij changes a gate Zacting on qubit ito act on qubit j. Thus, if we sandwich a Z(k)Z(l)term with the Uij ISWAP gate, we obtain UijZ(k)Z(l)U† ij =Z(τij(k))Z(τij(l)),(A3) where τij represents the permutation of the indices iand j.If k= i,j, then τij(k)=k, otherwise τij(i)=jand τij(j)=i. Without applying the ISWAP gate, the initial vertex permutation of the system is P=[1,2,...L]. After the ISWAP operation, the system is defined by the new permutation P=[τij(1),τ ij(2),τ ij(3),...,τ ij(L)]. This approach can be generalized to a system with arbitrary connections. To sum up, the ATA Ising Hamiltonian KLgraph is the sum of, at most, L(L−1)/2 HPs, each of them built by applying different permutations to a NN Ising Hamiltonian graph. [1]Y.I.Manin,Vychislimoe i nevychislimoe (Soviet Radio, Moscow, 1980). [2] R. P. Feynman, Simulating physics with computers, Int. J. Theor. Phys. 21,467 (1982). [3] P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Rev. 26, 1484 (1996). [4] L. K. Grover, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC) (ACM, New York, 1996). [5] P. J. Coles, S. Eidenbenz, S. Pakin, A. Adedoyin, J. Ambrosiano, P. Anisimov, W. Casper, G. Chennupati, C. Coffrin, H. Djidjev, D. Gunter, S. Karra, N. Lemons, S. Lin, A. Lokhov, A. Malyzhenkov, D. Mascarenas, S. Mniszewski, B. Nadiga, D. O’Malley, D. Oyen, L. Prasad, R. Roberts, 013012-7 MARTIN, LAMATA, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 013012 (2020) P. Romero, N. Santhi, N. Sinitsyn, P. Swart, M. Vuffray, J. Wendelberger, B. Yoon, R. Zamora, and W. Zhu, Quantum algorithm implementations for beginners, arXiv:1804.03719. [6] A. Martin, B. Candelas, Á. Rodríguez-Rozas, J. D. Martín- Guerrero, X. Chen, L. Lamata, R. Orús, E. Solano, and M. Sanz, Towards Pricing Financial Derivatives with an IBM Quantum Computer, arXiv:1904.05803. [7] K. Temme, S. Bravyi, and J. M. Gambetta, Error Mitigation for Short-Depth Quantum Circuits, Phys.Rev.Lett.119,180509 (2017). [8] S. Endo, S. C. Benjamin, and Y. Li, Practical Quantum Error Mitigation for Near-Future Applications, Phys.Rev.X8, 031027 (2018). [9] A. Chiesa, F. Tacchino, M. Grossi, P. Santini, I. Tavernelli, D. Gerace, and S. Carretta, Quantum hardware simulating fourdimensional inelastic neutron scattering, Nat. Phys. 15,455 (2019). [10] A. Kandala, K. Temme, A. D. Co´ rcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta, Error mitigation extends the computational reach of a noisy quantum processor, Nature (London) 567,491 (2019). [11] S. McArdle, X. Yuan, and S. Benjamin, Error-Mitigated Digital Quantum Simulation, Phys. Rev. Lett. 122,180501 (2019). [12] A. Parra-Rodriguez, P. Lougovski, L. Lamata, E. Solano, and M. Sanz, Digital-analog quantum computation, arXiv:1812.03637. [13] J. L. Dodd, M. A. Nielsen, M. J. Bremner, and R. T. Thew, Universal quantum computation and simulation using any entangling Hamiltonian and local unitaries, Phys. Rev. A 65, 040301 (2002). [14] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, U.K., 2000). [15] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum Algorithm for Linear Systems of Equations, Phys. Rev. Lett. 103,150502 (2009). [16] S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum principal component analysis, Nat. Phys. 10,631 (2014). [17] B. P. Lanyon, C. Hempel, D. Nigg, M. Müller, R. Gerritsma, F. Zähringer, P. Schindler, J. T. Barreiro, M. Rambach, G. Kirchmair, M. Hennrich, P. Zoller, R. Blatt, and C. F. Roos, Universal digital quantum simulation with trapped ions, Science 334,57 (2011). [18] E. A. Martinez, C. A. Muschik, P. Schindler, D. Nigg, A. Erhard, M. Heyl, P. Hauke, M. Dalmonte, T. Monz, P. Zoller, and R. Blatt, Real-time dynamics of lattice gauge theories with a few-qubit quantum computer, Nature (London) 534,516 (2016). [19] R. Barends, L. Lamata, J. Kelly, L. García-Álvarez, A. G. Fowler,A.Megrant,E.Jeffrey,T.C.White,D.Sank, J. Y. Mutus, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, E. Solano, and J. M. Martinis, Digital quantum simulation of fermionic models with a superconducting circuit, Nat. Commun. 6,7654 (2015). [20] Y. Salathé, M. Mondal, M. Oppliger, J. Heinsoo, P. Kurpiers, A. Potocˇ nik, A. Mezzacapo, U. Las Heras, L. Lamata, E. Solano, S. Filipp, and A. Wallraff, Digital Quantum Simulation of Spin Models with Circuit Quantum Electrodynamics, Phys.Rev.X 5,021027 (2015). [21] R. Barends, A. Shabani, L. Lamata, J. Kelly, A. Mezzacapo, U. Las Heras, R. Babbush, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, D. Sank, A. Vainsencher, J. Wenner, T. C. White, E. Solano, H. Neven, and J. M. Martinis, Digitized adiabatic quantum computing with a superconducting circuit, Nature (London) 534,222 (2016). [22] N. K. Langford, R. Sagastizabal, M. Kounalakis, C. Dickel, A. Bruno, F. Luthi, D. J. Thoen, A. Endo, and L. DiCarlo, Experimentally simulating the dynamics of quantum light and matter at deep-strong coupling, Nat. Commun. 8,1715 (2017). [23] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature (London) 549,242 (2017). [24] N. Klco, E. F. Dumitrescu, A. J. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, and M. J. Savage, Quantum-classical computation of Schwinger model dynamics using quantum computers, Phys.Rev.A98,032331 (2018). [25] F. Albarrán-Arriagada, J. C. Retamal, E. Solano, and L. Lamata, Measurement-based adaptation protocol with quantum reinforcement learning, Phys.Rev.A98,042315 (2018). [26] J. Olivares-Sánchez, J. Casanova, E. Solano, and L. Lamata, Measurement-based adaptation protocol with quantum reinforcement learning in a Rigetti quantum computer, arXiv:1811.07594. [27] Y. Ding, L. Lamata, J. D. Martín-Guerrero, E. Lizaso, S. Mugel, X. Chen, R. Orús, E. Solano, and M. Sanz, Towards Prediction of Financial Crashes with a D-Wave Quantum Computer, arXiv:1904.05808. [28] R. Sweke, M. Sanz, I. Sinayskiy, F. Petruccione, and E. Solano, Digital quantum simulation of many-body non-Markovian dynamics, Phys.Rev.A94,022317 (2016). [29] L. García-Álvarez, U. Las Heras, A. Mezzacapo, M. Sanz, E. Solano, and L. Lamata, Quantum chemistry and charge transport in biomolecules with superconducting circuits, Sci. Rep. 6,27836 (2016). [30] D. Ballester, G. Romero, J. J. García-Ripoll, F. Deppe, and E. Solano, Quantum Simulation of the Ultrastrong-Coupling Dynamics in Circuit Quantum Electrodynamics, Phys.Rev.X 2,021007 (2012). [31] A. Mezzacapo, U. Las Heras, J. S. Pedernales, L. DiCarlo, E. Solano, and L. Lamata, Digital quantum Rabi and Dicke models in superconducting circuits, Sci. Rep. 4,7482 (2014). [32] J. S. Pedernales, I. Lizuain, S. Felicetti, G. Romero, L. Lamata, and E. Solano, Quantum Rabi model with trapped ions, Sci. Rep. 5,15472 (2015). [33] J. Braumüller, M. Marthaler, A. Schneider, A. Stehli, H. Rotzinger, M. Weides, and A. V. Ustinov, Analog quantum simulation of the Rabi model in the ultra-strong coupling regime, Nat. Commun. 8,779 (2017). [34] D. Lv, S. An, Z. Liu, J.-N. Zhang, J. S. Pedernales, L. Lamata, E. Solano, and K. Kim, Quantum Simulation of the Quantum Rabi Model in a Trapped Ion, Phys.Rev.X8,021027 (2018). [35] A. Mezzacapo, M. Sanz, L. Lamata, I. L. Egusquiza, S. Succi, and E. Solano, Quantum simulator for transport phenomena in fluid flows, Sci. Rep. 5,13153 (2015). [36] S. Felicetti, M. Sanz, L. Lamata, G. Romero, G. Johansson, P. Delsing, and E. Solano, Dynamical Casimir Effect 013012-8 DIGITAL-ANALOG QUANTUM ALGORITHM FOR THE … PHYSICAL REVIEW RESEARCH 2, 013012 (2020) Entangles Artificial Atoms, Phys.Rev.Lett.113,093602 (2014). [37] D. Z. Rossatto, S. Felicetti, H. Eneriz, E. Rico, M. Sanz, and E. Solano, Entangling polaritons via dynamical Casimir effect in circuit quantum electrodynamics, Phys. Rev. B 93,094514 (2016). [38] M. Sanz, W. Wieczorek, S. GrÖblacher, and E. Solano, Electromechanical Casimir effect, Quantum 2,91 (2018). [39] L. García-Álvarez, J. Casanova, A. Mezzacapo, I. L. Egusquiza, L. Lamata, G. Romero, and E. Solano, Fermion-Fermion Scattering in Quantum Field Theory with Superconducting Circuits, Phys. Rev. Lett. 114,070502 (2015). [40] I. Arrazola, J. S. Pedernales, L. Lamata, and E. Solano, Digitalanalog quantum simulation of spin models in trapped ions, Sci. Rep. 6,30534 (2016). [41] L. Lamata, A. Parra-Rodriguez, M. Sanz, and E. Solano, Digital-analog quantum simulations with superconducting circuits, Adv. Phys. X 3,1457981 (2018). [42] D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. London, Ser. A 400,97 (1985). [43] A. Galicia, Digital-Analog Quantum Computing, Bachelor Thesis, University of the Basque Country (UPH/EHU), 2019. 013012-9