Enhanced Connectivity of Quantum Hardware with Digital-Analog Control

PHYSICAL REVIEW RESEARCH 2, 033103 (2020) Enhanced connectivity of quantum hardware with digital-analog control Asier Galicia ,1Borja Ramon ,1Enrique Solano,1,2,3,4and Mikel Sanz 1,2,3,* 1Department of Physical Chemistry, University of the Basque Country, Apartado 644, 48080 Bilbao, Spain 2IQM, Nymphenburgerstrasse 86, 80636 Munich, Germany 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 23 December 2019; accepted 23 June 2020; published 20 July 2020) Quantum computers based on superconducting circuits are experiencing rapid development, with the aim to outperform classical computers in certain useful tasks in the near future. However, the currently available chip fabrication technologies limit the capability of gathering a large number of high-quality qubits in a single superconducting chip, a requirement for implementing quantum error correction. Furthermore, achieving high connectivity in a chip poses a formidable technological challenge. Here, we propose a hybrid digital-analog quantum algorithm that enhances the physical connectivity among qubits coupled by an arbitrary inhomogeneous nearest-neighbor Ising Hamiltonian and generates an arbitrary all-to-all Ising Hamiltonian only by employing single-qubit rotations. Additionally, we optimize the proposed algorithm in the number of analog blocks and in the time required for the simulation. These results take advantage of the natural evolution of the system by combining the flexibility of digital steps with the robustness of analog quantum computing, allowing us to improve the connectivity of the hardware and the efficiency of quantum algorithms. DOI: 10.1103/PhysRevResearch.2.033103 I. INTRODUCTION Quantum computation has emerged in recent years as a promising technology which aims at solving problems such as the factorization of a composite number [1], studying quantum field theories [2,3], simulating quantum chemistry [4,5] and fluid dynamics [6], and simulating complex systems [7–10] more efficiently than classical computation. Another reason for the increasing interest in the field of quantum computation is due to Grover’s algorithm [11], which shows quadratic speedups when compared against classical search algorithms. This technology can be implemented in different quantum platforms, such as trapped ions, photonics, or superconducting qubits, among others. In this last platform, strong efforts have been performed to show an example in which a quantum processor outperforms any classical computer, a milestone recently achieved by Google [12]. This flourishing technology still presents a considerable number of challenges to be solved, such as increasing the number of high-quality qubits in a single quantum processor or achieving interactions among all qubits. These problems characterize the so-called noise intermediate-scale quantum (NISQ) devices [13], quantum chips comprising 50–100 qubits, which are still affected by significant noise. *[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. With the objective of optimizing the currently available resources for quantum computation and, ultimately, implementing a useful quantum computer in the NISQ era, an alternative paradigm of quantum computing, called digitalanalog quantum computation (DAQC) [14–16], has recently been proposed. The DAQC paradigm aims at improving the fidelity of the algorithm by exploiting the robustness of the natural dynamics provided by the quantum platform together with the flexibility given by the fast implementation of single qubit rotation (SQR). Recently, a constructive method to achieve universal quantum computation employing an all-to-all (ATA) Ising Hamiltonian as the analog resource has been proposed in Ref. [15]. Afterward, the implementation of relevant quantum algorithms within the DAQC paradigm has also been addressed with the digital-analog quantum Fourier transform (QFT) [17] and the quantum approximate optimization algorithm (QAOA) [18]. In these references, the authors numerically compared the performance of the DAQC paradigm against the purely digital one under sensible noise sources, showing the former gives remarkably better results when the system scales up with the number of qubits. The intrinsic connectivity among qubits in a quantum platform is not necessarily well described by an ATA homogeneous Hamiltonian. In fact, a realistic quantum chip is expected to present lower connectivity focused on approximately nearest-neighbor (NN) interactions, since ATA connections require a prohibitively increasing amount of wiring among qubits. In this paper, we design an algorithm that optimally simulates an arbitrary ATA Ising Hamiltonian employing as a resource a given inhomogeneous NN Ising model and SQR. 2643-1564/2020/2(3)/033103(11) 033103-1 Published by the American Physical Society GALICIA, RAMON, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 033103 (2020) 1 2 3 4 5 (a) 1 2 3 4 5 (b) 1 2 3 4 5 (c) FIG. 1. Examples of Ising Hamiltonians as their graph representation. Panel (a) shows a complete K5graph, which represents an all-to-all Hamiltonian HATA (g) for five qubits. Panel (b) shows a Hamiltonian path which represents a nearest-neighbor Hamiltonian HNN(g) for five qubits. Panel (c) shows another Hamiltonian path with the vertex permutation P=[1,3,4,2,5]. This is achieved employing O(5L2) analog blocks, i.e., NN evolutions, with Lbeing the number of qubits of the chip. Even though the particular dynamics considered as a resource is the ZZ Ising Hamiltonian, the proposed algorithm could be extended to other dynamics, such as the XX +YY Ising Hamiltonian. The simulation of the Hamiltonian is optimal in the dependence of the number of analog blocks and the simulation time required for these analog blocks. II. GRAPH REPRESENTATION OF AN ISING HAMILTONIAN The Ising Hamiltonian for Lqubits can be interpreted as a weighted graph of Lvertices, where the weight of the edge connecting the vertex ito the vertex jis gij. If two vertices i and jare not connected, gij =0. In this representation, an ATA Ising Hamiltonian of L qubits becomes a complete graph KL, i.e., a graph with edges among every possible vertex without repetition. On the other hand, the NN Ising Hamiltonian is represented as a Hamiltonian path, that is, a path visiting all the possible vertices only once. It is noteworthy to mention that an arbitrary Hamiltonian path is represented by a permutation of all the vertices in the graph. To recover a Hamiltonian path from a given vertex permutation, it suffices to connect with an edge the vertices that are adjacent in the permutation. An example of a complete graph, together with two Hamiltonian paths, is represented in Fig. 1, where we also show the vertex permutation of the Hamiltonian paths. Notice that we are currently dealing with ZZ interactions, and thus different Hamiltonian path evolutions commute. This means that the final evolution will be the sum of all the Hamiltonian paths weighted by their respective evolution time. This last statement is summarized in the equation  i eitiHPi(gj)=eiitiHPi(gj),(1) where HPi(gj) is a Hamiltonian that describes a ZZ interaction which has a graph representation of a Hamiltonian path with weights gj. This is understood in the graph representation as having as final graph the sum of all the weighted Hamiltonian paths. Our first task is then to split the complete graph, which represents the ATA Hamiltonian, into a set of Hamiltonian =++ (b) (c) (d)(a) 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 FIG. 2. An example of how to fill exactly a complete graph of six vertices using Hamiltonian paths. Panel (a) represents the complete graph we are trying to obtain. Panels (b), (c), and (d) correspond to the Hamiltonian paths we use. Panel (b) is built by starting in the first node, going forward to the next node, then two nodes backward, three forward, etc. The other two Hamiltonian paths are obtained by rotating the first one. From this construction technique, we obtain Hamiltonian paths defined by the permutations of Eq. (2). The permutations that define panels (b), (c), and (d) are respectively P1 6= [1,2,6,3,5,4], P2 6=[2,3,1,4,6,5], and P3 6=[3,4,2,5,1,6]. paths that will be later simulated using our resource (the NN Hamiltonian). This will allow us to efficiently decompose the ATA evolution in terms of Hamiltonian paths. Partitioning a complete graph into a set of Hamiltonian paths resembles the Hamiltonian decomposition problem, which is about partitioning a complete graph into a set of Hamiltonian cycles. This last problem was solved by Walecki [19,20] in 1890, who used a construction in which one Hamiltonian cycle is rotated to get all the cycles that compose the complete graph. Using a similar decomposition schematized for six qubits in Fig. 2, we can decompose the complete graph into a set of disjoint Hamiltonian paths. These Hamiltonian paths are characterized by the vertex permutation Pk L(j)=k−1+j 2mod L+1,if jeven, k−1−j−1 2mod L+1,if jodd, (2) where Pk L∈SL,SLis the symmetric group for Lelements, L is the number of qubits, and k∈Zsuch that 1 ⩽k⩽L/2. j represents the jth position of the vertex permutation. Note that kis just a label for the Hamiltonian path. It is also noteworthy to mention that this partition is only valid for an even number of qubits. When dealing with an odd number of qubits, and hence, and odd number of vertex in the graph representation, we use the notion of single perfect matching. This involves using the same Hamiltonian path construction of Eq. (2), but allowing one Hamiltonian path to overlap with the rest. This will pose no problem in our later construction, since we will be able to selectively turn off the desired interactions. In Fig. 2, we show an example for six qubits where we also depicted the corresponding Hamiltonian paths. Hence, the problem now consists on efficiently simulating these Hamiltonian paths to obtain the ATA evolution. III. SWAPPING GATES The next step is to obtain each of the Hamiltonian path connections using a NN Hamiltonian as a resource. For that, we will change the connections using a SWAP-like gate Uthat 033103-2 ENHANCED CONNECTIVITY OF QUANTUM HARDWARE … PHYSICAL REVIEW RESEARCH 2, 033103 (2020) performs the operations U(σz⊗I)U†=I⊗σz, U(I⊗σz)U†=σz⊗I.(3) The gate that changes the action of an arbitrary operator in a qubit to another qubit is the SWAP gate, defined as USWAP =eiπ 4(X1X2+Y1Y2+Z1Z2),(4) where the superindices 1 and 2 refer to the qubit on which the gate acts. However, as we only need to change Zgates, we have some degrees of freedom available. More precisely, the most general unitary gate that fulfils Eq. (3)is U(α,β, γ )=R1 zπγ−α 2+1 2+β ×eiπ 4(X1X2+Y1Y2+(γ+α)Z1Z2) ×R1 zπγ−α 2−1 2−β,(5) where R1 z[θ]=eiσ1 z θ 2and α,β, γ ∈R. Since we will later build this gate using inhomogeneous Ising Hamiltonians from the DAQC perspective, we will set α=γ=0 and β=− 1 2, obtaining the so-called iSWAP gate. The choice of parameters will minimize the amount of singlequbit gates and analog blocks required, since UiSWAP =eiπ 4(X1X2+Y1Y2).(6) We will focus now on obtaining a sequence of iSWAP gates acting on adjacent qubits that efficiently transforms a system with NN connections into a system with the desired Hamiltonian path connections. The reason to restrict ourselves to adjacent iSWAP gates is that we want to decompose them using NN Ising Hamiltonians as a resource. For the sake of clarity, we will use Uij to represent the iSWAP gate between qubits iand j. We will first show how this operation transforms a system with NN couplings. The result will be a system represented by a Hamiltonian path in its graph representation. If we sandwich σk zσl z, a gate that applies the Zgate to the qubits kand l, with the gate Uij, we obtain Uijσk zσl zU† ij =στij(k) zστij(l) z,(7) where we have defined the function τij as a permutation of the indices iand j, that is, a transposition. More precisely, if k= i,j,τij(k)=k, otherwise, τij(i)=jand τij(j)=i. Basically, the Uij gate changes σzgates acting on qubit ito act on qubit j. Because of the unitarity of the iSWAP operation, its action on a NN Hamiltonian evolution can be written as UijeitH(g)NNU† ij =eitUijH(g)NNU† ij. Therefore, the final Hamiltonian results in UijHNN(g)U† ij = L−1  k=1 gUijσk zσk+1 zU† ij = L−1  k=1 gστij(k) zστij(k+1) z.(8) The initial vertex permutation defining the system’s NN coupling was P =[1,2,3, ..., L]. After the iSWAP operation, the permutation that defines our system is P= [τij(1),τ ij(2),τ ij(3), ..., τij(L)]. This approach is straightforwardly generalized to a system with arbitrary connections. This means that, after sandwiching with iSWAP gates a system with certain connections, it interchanges the ones that had the two qubits being affected by the iSWAP gate. In our case, since we will be dealing with systems represented by a Hamiltonian path, the iSWAP operation reduces to a transposition in the corresponding vertex permutation. As the set of transpositions that our NN resource can implement, {τii+1}for i∈[1,L−1], is a generator of the symmetric group SL, we can obtain any desired permutation using the correct transpositions. This means that we can simulate the evolution of any system with couplings represented by a Hamiltonian path using as resource the system with NN couplings. For example, the Ising Hamiltonian that represents Fig. 1(c), which we will call H1, is just obtained using the following transformations H1(g)=U34U23HNN(g)U† 23U† 34. For the sake of simplicity, we will define a sequence of transpositions to be Si→j=τii+1τi+2i+3...τj−1jif i<j Iif i⩾j.(9) The permutations defined in Eq. (2) can be composed in terms of two groups of sequences, G1(k)=S2k−2 1→2S2k−3 2→3··· ×S4 1→2k−4S3 2→2k−3S2 1→2k−2S1 2→2k−1,(10) G2(k,L)=SL−2k−1 L−1→LSL−2k−2 L−2→L−1··· ×S4 2k+4→L−1S3 2k+3→LS2 2k+2→L−1S1 2k+1→L,(11) where kand Lrefer to the permutation Pk Lwe are building and the sequences have been labeled to make clear the order of application. That is, Pk L=G1(k)G2(k,L). In Appendix A,we prove that these are indeed the groups of sequences needed to obtain the desired permutations of Eq. (2). Note that both groups of sequences commute between them. Let us now show an example for the case of six qubits. In order to obtain the permutation P3 6from Fig. 3, we need to apply the transpositions defined in Eq. (11), which are G1(3) and G2(3,6). However, in the particular case of G2(3,6), since 2 ×k+1=7 and L=6, G2(3,6) =I. The sequences applied are G1(3) =S4 1→2S3 2→3S2 1→4S1 2→5. The circuit that implements this set of transpositions using iSWAP gates is shown in Fig. 3, where each column of iSWAP gates represents one sequence of transpositions. To sum up, in this section we have shown an algorithm that, using adjacent iSWAP gates and the NN Ising Hamiltonian as resource, is able to simulate the evolution of an ATA Hamiltonian for the case of an even number of qubits. Let us now simplify the circuit so that it requires the smallest possible amount of iSWAP gates. 033103-3 GALICIA, RAMON, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 033103 (2020) 1 2 3 6 5 4 1 2 3 6 5 4 FIG. 3. Circuit that simulates the evolution of a Hamiltonian path with vertex permutation P3 6. Each of the surrounding columns of iSWAP gates is related with one of the sequences belonging to the groups defined in Eq. (11). IV. SIMPLIFICATION OF THE CIRCUIT In this section, we will show an optimized version of the previously discussed circuit. Besides, we will also give a decomposition of the circuit in terms of ZZ gates, which will be useful later. Since we now need to combine the set of Hamiltonian paths {Pk L}to obtain the desired ATA evolution, it is possible to simplify the total number of iSWAP (U) gates needed. The total circuit is described by the set of gates, F(k,L)= 2k+1  i=2,ieven Ui,i+1 L−1  i=2k+1,ieven U† i,i+1 × 2k  i=1,iodd Ui,i+1 L−1  i=2k+1,iodd U† i,i+1, ×k∈1,L 2−1,F(0,L) = j=1  j=L 2 ⎡ ⎣ L−1  i=2j−1,iodd Ui,i+1 L−2  i=2j−2,ieven Ui,i+1⎤ ⎦, FL 2,L= j=L 2  j=1L−2j  i=1,iodd U† i,i+1 L+1−2j  i=2,ieven U† i,i+1.(12) The final ATA evolution will be described as eitfHATA =⎡ ⎣ L 2  k=1 F(k,L)eitfHNN ⎤ ⎦F(0,L).(13) In Appendix C, we show the demonstration leading to this simplified circuit. In Fig. 4, we show an example of the simplification for the case of six qubits. Using Eq. (5), we can decompose the gates F(k,L)into a set of SQR and ZZi,j(φ=gjtf) gates acting on adjacent qubits. Grouping parallel ZZij gates naturally leads to a circuit which can be implemented using the DAQC protocol, as explained in the following section. An example for the case of six qubits is shown in Fig. 5. We now take into account that two consecutive parallel sets of iSWAP gates can be decomposed into three analog blocks plus some SQR (as will be proven in the next section). Since the total number of F(k,L)fork∈[1,L 2−1] gates is L 2−1 and each one requires two parallel sets of iSWAP gates, we require a total of 3L 2−3 analog blocks to generate these gates. We also need at most 3(L 2−2) analog gates to implement the F(0,L) set of gates and 3(L 2−1) analog gates to implement F(L 2,L). Moreover, we need L 2analog blocks more evolving during a time tf. The total amount of inhomogeneous analog blocks needed is then 5L−12. In the following section, given a NN inhomogeneous Hamiltonian with fixed couplings, we will derive an algorithm to simulate the evolution of an arbitrary NN inhomogeneous Hamiltonian efficiently, both in time and in the number of analog blocks. This is the last step before obtaining an algorithm to simulate an arbitrary inhomogeneous ATA Hamiltonian. V. SIMULATING AN ARBITRARY INHOMOGENEOUS HAMILTONIAN In this section, we will show an algorithm to simulate the evolution of an arbitrary inhomogeneous NN Hamiltonian under the paradigm of DAQC, employing a similar algorithm to the one shown in Ref. [15]. In this case, our resource will be a fixed inhomogeneous NN Hamiltonian. The algorithm we use has the following three advantages over the one shown in Ref. [15]: (i) It works for an arbitrary number of qubits, (ii) it requires the minimum amount of analog blocks, and (iii) it optimizes the time required for the simulation. We will first need to notice that it is possible to selectively change the sign of any desired combination of couplings. This is done by surrounding some of the qubits with Xgates. We represent the action of the Xgates by colouring the corresponding qubits in the graph representation (see Fig. 6). In order to change the sign of the desired combination of couplings, it suffices to color differently the qubits connected to the desired couplings. In Appendix B, we prove that this can be done for a NN chain with an arbitrary length. In Fig. 6, we change the sign of all the couplings in Fig. 6(a) and the sign of just one coupling in Fig. 6(b). We will now decompose a HNN(g j) evolution during a time tfinto a set of HNN(gj) evolutions that have been evolving 033103-4 ENHANCED CONNECTIVITY OF QUANTUM HARDWARE … PHYSICAL REVIEW RESEARCH 2, 033103 (2020) (a) (b) (c) (d) 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 FIG. 4. Simplified circuit simulating an ATA Hamiltonian evolution. Panel (a) shows the three Hamiltonian paths that form the ATA evolution. Panel (b) is obtained by introducing the iSWAP gates that transform a NN Hamiltonian in the desired Hamiltonian paths. This gates are described by the group of transpositions defined in Eqs. (10)and(11). The set of transpositions obtained with this equation is translated into a set of iSWAP/iSWAP†gates surrounding the NN Hamiltonian as discussed in Sec. III. In panel (c), we simplify the circuit by making use of iSWAP iSWAP†=I. The resulting gates are the set of iSWAP gates defined in Eq. (12), which lead to the circuit depicted in panel (d). during a time tneach: tfHNN(g j)=tf L−1  j=1 g jσj zσj+1 z = L−1  j=1 L−1  n=1 tngj(−1)fn(j)+fn(j+1)σj zσj+1 z = L−1  j=1 L−1  n=1 tnL−1  k=1 Xfn(k) kgjσj zσj+1 zL−1  k=1 Xfn(k) k = L−1  n=1 tnL−1  k=1 Xfn(k) kHNN(gj)L−1  k=1 Xfn(k) k,(14) where Xj iis an Xgate applied on the ith qubit jtimes and fn(k) is a binary function that determines whether an Xgate is being applied in the kth qubit during the nth analog block, yet to be determined. In the first step, we make use of bj=g j gj = L−1  n=1 Mnj tn tf ,(15) where Mnj =(−1)fn(j)+fn(j+1). This defines the following system of linear equations, b=Mt tf .(16) The matrix Mhas only ±1 entries. The interpretation of Mnj =−1 is that during the nth analog block, the jth coupling changes the sign. From now on, we will only focus on the M matrix instead of the fn(j) functions. 033103-5 GALICIA, RAMON, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 033103 (2020) 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 FIG. 5. This circuit is obtained by replacing each iSWAP in Fig. 4by the expression shown in Eq. (6), where each of the exponentials have been multiplied by the appropriate single-qubit gates to transform them into ZZ interactions. Then, these interactions are gathered and expressed as evolutions of NN Ising Hamiltonians, characterized by the different couplings gand their evolution time tf. Each of these inhomogeneous Hamiltonian evolutions can be implemented using the DAQC circuit discussed in Sec. V. The SQR employed in this circuit are the Hadamard gate (H) and the gate R,definedasR=HSH,whereSis the phase gate. We will now assume without loss of generality that the following conditions hold ∀j: bj⩾bj+1,(17) |b1|⩾|bj|,(18) bj>0.(19) Without loss of generality, bjcan always be relabeled and have their signs changed to hold these inequalities. Under these conditions, we propose the following Mmatrix: M= ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1111··· 1111 −1111··· 1111 −1−111 1111 −1−1−11 ...1111 . . .. . .. . ........... . .. . .. . . −1−1−1−1...1111 −1−1−1−1...−1111 −1−1−1−1··· −1−111 −1−1−1−1··· −1−1−11 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . (20) After inverting this matrix (see Appendix D), Eq. (16) leads to the time intervals tk tf =bk−bk+1 2,(21) tL−1 tf =b1+bL−1 2,(22) with k∈[1,L−2]. Recall that tk=0 means that we do not need the kth analog block for the simulation. Let us now prove that these solutions for tnimply the minimum amount of analog blocks and that the time required for the simulation is minimal. As, through Eqs. (21) and (22), we are mapping the set of times {tn}L−1 n=1to the values {bj}L−1 j=1, we need at least as much different tnas bj. Indeed, suppose that bj=bj. We can relabel them such that j=j+1. Then, from Eq. (21), we get that tj=0, so the total number of analog blocks is reduced by 1. Another particularly relevant case is when bj=0forkdifferent values, for which the number of analog blocks needed is reduced by k−1. The time required to simulate the desired HNN(g j)is defined as tsim =L−1 n=1|tn|. Note that we do not take into account the time required to implement the Xgates since we are supposing that they are ideal digital blocks, instantaneous. However, we believe that the circuit will still be minimum in time as long as we can parallelize the application of these gates. In Appendix E, we prove that, (a) (b) FIG. 6. Colored graphs representing the surrounding of Xgates in the evolution of a NN system for five qubits. A colored node corresponds to a qubit surrounded by Xgates. The dotted lines represent the change of sign in the coupling. Panel (a) represents the inversion of all couplings, which is the same as inverting the time evolution of the system. Panel (b) represents the inversion of only one of the couplings. 033103-6 ENHANCED CONNECTIVITY OF QUANTUM HARDWARE … PHYSICAL REVIEW RESEARCH 2, 033103 (2020) (a ) (b ) (c ) FIG. 7. Implementation of the circuit discussed in Sec. V. The digital block implemented is used in the circuit of Fig. 5to generate an iSWAP gate between qubits 2 and 3, in parallel with an iSWAP†gate between qubits 4 and 5. The analog blocks shown in the right-hand side of panel (a) represent the evolution of a NN system, where the sign of some of the couplings have been inverted according to Eq. (20). The different evolution times are determined by Eqs. (21)and(22). In order to meet the constraints imposed by Eqs. (17)–(19), the coefficients b1,b2,b3,b4,andb5are equal to g 2 g2,g 4 g4,g 1 g1,g 3 g3,andg 5 g5, respectively (we made the assumption that g4>g2). Since b2<0, we need to change g4of sign in all the analog blocks, which is achieved by applying the Xgates of panel (a). The dashed lines in the analog block represent a coupling changed of sign. These dashed lines connects two qubits with different color, whereas a solid line connects two qubits with the same color. The change of sign of the ith coupling (bi) is given by the ith column of the matrix defined in Eq. (20). For example, the first column of the matrix shows that all the signs of bibelonging to the first block must be inverted except from b1, which is related to g2. Consequently, all the signs of the couplings must be inverted, except from g2. In panel (b), we sandwiched each analog block with Xgates in the qubits that were colored, representing in that way the same evolution of panel (a). We also show the time evolution corresponding to each analog block. Lastly, in panel (c) we simplified the previous circuit both by eliminating all the analog blocks with zero time evolution, and all unnecessary Xgates, taking into account that XX =I. under the constrains of Eqs. (17)–(19), min(tsim)≡tmin = |b1|tf. We also prove in Appendix Ethat our circuit requires a time tmin to perform the simulation of an arbitrary inhomogenous Hamiltonian, which is the minimum time possible. As an example, in Fig. 7we represent the implementation of one of the analog blocks shown in Fig. 5, required for a set of iSWAP gates. More precisely, the depicted block is necessary for an iSWAP gate between the qubits 2 and 3 and an iSWAP† gate between the qubits 4 and 5. It is noteworthy to mention that we require at least L−1 analog blocks to simulate the evolution of an arbitrary inhomogeneous NN Hamiltonian. Until now, we have shown an algorithm that simulates the evolution of an homogeneous ATA Hamiltonian using as resource an inhomogeneous NN Hamiltonian. Furthermore, it is attained with O(5L2) analog blocks, since we need 033103-7 GALICIA, RAMON, SOLANO, AND SANZ PHYSICAL REVIEW RESEARCH 2, 033103 (2020) O(5L) inhomogeneous analog blocks, each of which can be simulated using O(L) homogeneous analog resources. It is straightforward to modify the circuit in order to simulate an inhomogeneous ATA Hamiltonian with negligible impact on the performance. It suffices to change the analog blocks of Fig. 4for the necessary inhomogeneous NN Ising Hamiltonian. In order to implement this circuit for an odd number of qubits, L, we can use the same set of Hamiltonian paths, Pk L, of Eq. (2). In this case, k∈[1,L+1 2] and, in order to obtain an homogeneous ATA Hamiltonian, we need to set to zero some of the couplings used for the Hamiltonian path evolution representing P L+1 2 L. It should be noted that the number of analog blocks will still be O(5L2). Even though we do not discuss here how to obtain the iSWAP gates for this case, techniques similar to those discussed in Appendix Acan be employed. VI. CONCLUSIONS We have shown that, within the DAQC paradigm, naturally arising evolutions can be utilized to simulate any inhomogeneous ATA Ising Hamiltonian along with SQR. In particular, we have designed an algorithm based on a NN Ising Hamiltonian with O(5L2) analog blocks, where Lis the number of qubits in the chip. For this, we also discussed both a digital approach that simulates an ATA system while having NN-like connections and an algorithm that simulates under the DAQC paradigm the evolution of an inhomogeneous Hamiltonian. This last algorithm has been proven to be efficient in the number of analog blocks and in the simulation time required, as long as we treat SQR as ideal gates. This protocol can be extended to platforms described by different Hamiltonians, such us the XX +YY NN Ising Hamiltonian. 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 from the EU FET Open project 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 No. ERKJ333. APPENDIX A: GROUP DEMONSTRATION In this Appendix, we prove that the combination of sequences G1(k) and G2(k,L), defined in Eq. (11), decompose Pk Linto a set of adjacent transposition, that is, Pk L= G1(k)G2(k,L). For that, we will first briefly discuss how to state the problem in terms of the matrix representation of the permutation group [21]. For the sake of clarity, we will denote by Tkthe matrix representation of a transposition τk. The problem we are solving can be stated as obtaining a finite set of transpositions {Tk}M k=1that transforms the vector b with components biinto the vector bwith components bPk L(i). That is, M k=1Tkb=b. However, since T−1=T, this set of transpositions will hold that 1 k=MTkb=b. The decomposition of PL kis then Pk L=τ1◦τ2◦···◦τk, where we use b◦a=b(a) to denote the order of the operations. The only restriction we will impose in the available transpositions is that they need to be adjacent. Denoting by T(i,j) the transposition τi,jthat transposes the elements iand j, we note that T(i,j)btransposes the elements of bin the positions iand j. Hence, we can use algorithms, such as the Bubble Short algorithm or its parallelized version, to directly obtain an optimized set of transpositions Tkthat shorts a given vector b. Indeed, the set of transpositions G1and G2have been obtained using those techniques, though we considered it necessary to give a closed formula, which we now prove to be correct. We will now define ci,las the operation that fulfills ci,lPk L(j)=⎧ ⎨ ⎩ Pk L(j)ifj= i,l Pk L(i)ifj=l Pk L(l)ifj=i. (A1) That is, it changes the position of the entry iwith the entry l. We will define g1and g2as G1and G2in Eqs. (10) and (11) but with all the τij operations replaced by cij.Fromthe representation we see that replacing all the transpositions, τij for cij, makes the new group of operations g1and g2to fulfill the equation g1◦g2◦Pk L=1,(A2) where 1 stands for the identity permutation. This again resembles to shorting and array defined by Pk Lwhere the operations cij are the changes in positions made to that array. We continue by realizing that Pk L(j)=Pk 2k(j)ifj⩽2k, PL−2k L−2k(j−2k)+2kif j>2k,(A3) that is, we obtain two commuting permutations. This is why two commuting groups of sequences, G1(k) and G2(k,L), arise. Note that the second permutation, which can be regarded as PL Lwith L=L−2k, is obtained from G2(L)=SL−1 L−1→L◦SL−2 L−2→L−1◦··· ×···◦S4 4→L−1◦S3 3→L◦S2 2→L−1◦S1 1→L.(A4) G2(L) differs from G2(k,L) by a factor of 2kthat appears in all the sequences. This extra factor in G2(k,L) comes from Eq. (A3), where it appears adding to the permutation PL−2k L−2k.It has the effect of changing the action of all transpositions from τij to τi+2kj+2k. We will only prove how to short the permutation that fulfills g1(k)◦Pk 2k=1 because proving that g 2(L)◦PL L=1 requires the same steps. We will prove this by induction. Since g1(1) is the identity operation and P1 2is the identity permutation, it is clear that g1(1) ◦P1 2=1. We now suppose that g1(k−1) ◦Pk−1 2k−2=1 and we prove that, with this condition, g1(k)◦Pk 2k=1. Since g1(k)◦Pk 2k=g1(k−1) ◦ s1→2k−2◦s2→2k−1◦Pk 2k, it suffices to prove that s1→2k−2◦ s2→2k−1◦Pk 2k=Pk−1 2k−2, where si→jis defined in Eq. (9)but with all the τij operations replaced by cij operations. Notice that s2→2k−1has the effect of changing the position of all 033103-8 ENHANCED CONNECTIVITY OF QUANTUM HARDWARE … PHYSICAL REVIEW RESEARCH 2, 033103 (2020) the entries in Pk Lexcept for the last and the first one. All the numbers in an odd position change to their left position and all the number in a even position change to their right position. Hence, the permutation obtained from π1=s2→2k−1◦Pk 2k results in π1(j)=⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ Pk 2k(j+1) if jeven Pk 2k(j−1) if jodd Pk 2k(1) if j=1 Pk 2k(2k)ifj=2k =⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ Pk 2k(j+1) if jeven Pk 2k(j−1) if jodd 2kif j=2k , whereweusedPk 2k(0) =Pk 2k(1). We now compute the operation π2=s1→2k−2◦π1, which changes the position of all the entries except from the last two. Hence, π2(j)=⎧ ⎪ ⎨ ⎪ ⎩ π1(j−1) if jeven π1(j+1) if jodd π1(2k−1) if j=2k−1 π1(2k)ifj=2k =⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ Pk 2k(j−2) if jeven Pk 2k(j+2) if jodd 2k−1ifj=2k−1 2kif j=2k =⎧ ⎨ ⎩ Pk−1 2k−2(j)ifj<2k−1 2k−1ifj=2k−1 2kif j=2k . Since g1(k−1) does not affect to the positions 2kand 2k−1, g1(k−1) ◦π1(j) =⎧ ⎨ ⎩ g1(k−1) ◦Pk−1 2k−2(j)ifj<2k−1 2k−1ifj=2k−1 2kif j=2k =1. This completes the proof. APPENDIX B: COLORED GRAPHS DEMONSTRATION In order to prove that we can selectively change the sign of a coupling in an arbitrary length NN chain, we will use an induction process. If Lis the number of nodes in a NN chain, then k=L−1 is the number of couplings. Inverting the couplings for the k=1 case is trivial. Supposing that we can selectively change the coupling sign of the k=k−1, we will prove that we can do it for the case k=k. The construction relies in the fact that, in order to change the sign of the new coupling, it suffices to change the color of the newly added node. In this case, the color of the new node must be different form its neighbor’s color, which can always be achieved in the NN case. If we do not want to change the sign of the kcoupling, we just need to color the new node as its neighbor. APPENDIX C: DEMONSTRATION OF EQ. (12) In this Appendix, we show how to obtain the gates defined in Eq. (12). For that, we first define various set of gates that will simplify the notation. We define ˜ Sto be the set of iSWAP† gates that are obtained from substituting τij →iSWAP† ij in Eq. (9). At the same time, ˜ Gis defined to be the set of iSWAP† gates that are obtained from substituting S→˜ Sin Eqs. (10) and (11). Hence, it holds that HPPk L=˜ G1†˜ G2†HNN ˜ G2˜ G1,(C1) where HNN is the NN Hamiltonian and HP(Pk L)istheZZ interaction Hamiltonian described by the Hamiltonian Path Pk L. F(k,L) describes the gates between the NN Hamiltonians that will be used to implement the Hamiltonian paths with vertex permutation Pk Land Pk=1 L. Hence, F(k,L) =⎧ ⎪ ⎨ ⎪ ⎩ ˜ G† 1(k+1) ˜ G† 2(k+1,L)˜ G1(k)˜ G2(k,L)k∈1,L 2−1, ˜ G† 2(1,L)k=0, ˜ G1L 2k=L 2, (C2) where it is straightforward to prove that F(k,L) has the form described in Eq. (12)fork=0 and k=L 2.Fork∈[1,L 2− 1], we will prove that the set of iSWAP gates can be further simplified to obtain Eq. (12). We first note that the following equations hold from the definition of ˜ G, ˜ G1(k+1) =˜ G1(k)˜ S1→2k˜ S2→2k+1,(C3) ˜ G2(k,L)=˜ G2(k+1,L)˜ S2k+2→L−1˜ S2k+1→L.(C4) Hence, it follows that ˜ G† 1(k+1) ˜ G† 2(k+1,L)˜ G1(k)˜ G2(k,L) =˜ S† 2→2k+1˜ S† 1→2k˜ G† 1(k)˜ G† 2(k+1,L)˜ G1(k)˜ G2(k,L) =˜ S† 2→2k+1˜ S† 1→2k˜ G† 2(k+1,L)˜ G2(k,L) =˜ S† 2→2k+1˜ S† 1→2k˜ G† 2(k+1,L)˜ G2 ×(k+1,L)˜ S2k+2→L−1˜ S2k+1→L =˜ S† 2→2k+1˜ S† 1→2k˜ S2k+2→L−1˜ S2k+1→L, where we used that [ ˜ G† 1(k),˜ G† 2(k+1,L)] =0 and ˜ G† 1(k)˜ G1(k)=˜ G† 2(k+1,L)˜ G2(k+1,L)=I. We now have that F(k,L) =⎧ ⎪ ⎨ ⎪ ⎩ ˜ S† 2→2k+1˜ S† 1→2k˜ S2k+2→L−1˜ S2k+1→Lk∈1,L 2−1, ˜ G† 2(1,L)k=0, ˜ G1L 2k=L 2, (C5) 033103-9