Synthesis of and compilation with time-optimal multi-qubit gates

Pascal Baßler1, Matthias Zipper1, Christopher Cedzich1, Markus Heinrich1, Patrick H. Huber2, Michael Johanning2, and Martin Kliesch1,3

1Institute for Theoretical Physics, Heinrich-Heine-Universität Düsseldorf, Germany
2Department of Physics, School of Science and Technology, University of Siegen, Germany
3Institute for Quantum and Quantum Inspired Computing, Hamburg University of Technology, Germany

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We develop a method to synthesize a class of entangling multi-qubit gates for a quantum computing platform with fixed Ising-type interaction with all-to-all connectivity. The only requirement on the flexibility of the interaction is that it can be switched on and off for individual qubits. Our method yields a time-optimal implementation of the multi-qubit gates. We numerically demonstrate that the total multi-qubit gate time scales approximately linear in the number of qubits. Using this gate synthesis as a subroutine, we provide compilation strategies for important use cases: (i) we show that any Clifford circuit on $n$ qubits can be implemented using at most $2n$ multi-qubit gates without requiring ancilla qubits, (ii) we decompose the quantum Fourier transform in a similar fashion, (iii) we compile a simulation of molecular dynamics, and (iv) we propose a method for the compilation of diagonal unitaries with time-optimal multi-qubit gates, as a step towards general unitaries. As motivation, we provide a detailed discussion on a microwave controlled ion trap architecture with magnetic gradient induced coupling (MAGIC) for the generation of the Ising-type interactions.

To run a program on any computing platform, it is necessary to decompose its higher-level logical operations into more elementary ones, and eventually translate those into the native instruction set of the platform at hand. In this top-down approach this process is called compiling. It is not only crucial for classical, but also quantum computation. Complementary to a general compilation process, it is often useful to start with the native instruction set to develop dedicated constructions for particularly useful quantum gates –a process called gate synthesis– which can then be used for compiling. The performance of compiling and gate synthesis depends severely on the available interactions on the quantum computing platform and the extent to which they can be controlled.

In this work, we synthesize a class of multi-qubit quantum gates on a platform that satisfies the following abstract requirements:
(I) parallel execution of single-qubit rotations, and
(II) Ising interactions with all-to-all connectivity.
For the compilation strategies with these gates we additionally require that
(III) certain qubits can be excluded from the participation in the interaction.
These requirements are met by many platforms such as ion traps and superconducting qubits and provide multi-qubit entangling.
We synthesize time-optimal multi-qubit gates from sequences of Ising interactions with different qubit encodings during suitable time steps.

Using our gate synthesis as a subroutine, we provide compilation strategies for important use cases which include – but are not limited to – the simulation of molecular dynamics, the quantum Fourier transform, and Clifford circuits. The latter two are ubiquitous in important quantum algorithms like the Shor's algorithm for integer factoring and play an important role in the characterization of quantum computing platforms, e.g., via randomized benchmarking.

► BibTeX data

► References

[1] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018), arXiv:1801.00862.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79
arXiv:1801.00862

[2] D. A. Lidar and T. A. Brun, Quantum error correction (Cambridge University Press, 2013).
https:/​/​www.cambridge.org/​core/​books/​quantum-error-correction/​B51E8333050A0F9A67363254DC1EA15A

[3] X. Wang, A. Sørensen, and K. Mølmer, Multibit gates for quantum computing, Phys. Rev. Lett. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https:/​/​doi.org/​10.1103/​PhysRevLett.86.3907
arXiv:quant-ph/0012055

[4] T. Monz, P. Schindler, J. T. Barreiro, M. Chwalla, D. Nigg, W. A. Coish, M. Harlander, W. Hänsel, M. Hennrich, and R. Blatt, 14-qubit entanglement: Creation and coherence, Phys. Rev. Lett. 106, 130506 (2011), arXiv:1009.6126.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.130506
arXiv:1009.6126

[5] N. M. Linke, D. Maslov, M. Roetteler, S. Debnath, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Experimental comparison of two quantum computing architectures, PNAS 114, 3305 (2017), arXiv:1702.01852.
https:/​/​doi.org/​10.1073/​pnas.1618020114
arXiv:1702.01852

[6] E. A. Martinez, T. Monz, D. Nigg, P. Schindler, and R. Blatt, Compiling quantum algorithms for architectures with multi-qubit gates, New J. Phys. 18, 063029 (2016), arXiv:1601.06819.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​6/​063029
arXiv:1601.06819

[7] D. Maslov and Y. Nam, Use of global interactions in efficient quantum circuit constructions, New J. Phys. 20, 033018 (2018), arXiv:1707.06356.
https:/​/​doi.org/​10.1088/​1367-2630/​aaa398
arXiv:1707.06356

[8] J. van de Wetering, Constructing quantum circuits with global gates, New J. Phys. 23, 043015 (2021), arXiv:2012.09061.
https:/​/​doi.org/​10.1088/​1367-2630/​abf1b3
arXiv:2012.09061

[9] N. Grzesiak, A. Maksymov, P. Niroula, and Y. Nam, Efficient quantum programming using EASE gates on a trapped-ion quantum computer, Quantum 6, 634 (2022), arXiv:2107.07591.
https:/​/​doi.org/​10.22331/​q-2022-01-27-634
arXiv:2107.07591

[10] S. Bravyi, D. Maslov, and Y. Nam, Constant-cost implementations of Clifford operations and multiply controlled gates using global interactions, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https:/​/​doi.org/​10.1103/​PhysRevLett.129.230501
arXiv:2207.08691

[11] C. Figgatt, A. Ostrander, N. M. Linke, K. A. Landsman, D. Zhu, D. Maslov, and C. Monroe, Parallel entangling operations on a universal ion-trap quantum computer, Nature 572, 368 (2019), arXiv:1810.11948.
https:/​/​doi.org/​10.1038/​s41586-019-1427-5
arXiv:1810.11948

[12] Y. Lu, S. Zhang, K. Zhang, W. Chen, Y. Shen, J. Zhang, J.-N. Zhang, and K. Kim, Global entangling gates on arbitrary ion qubits, Nature 572, 363 (2019), arXiv:1901.03508.
https:/​/​doi.org/​10.1038/​s41586-019-1428-4
arXiv:1901.03508

[13] N. Grzesiak, R. Blümel, K. Wright, K. M. Beck, N. C. Pisenti, M. Li, V. Chaplin, J. M. Amini, S. Debnath, J.-S. Chen, and Y. Nam, Efficient arbitrary simultaneously entangling gates on a trapped-ion quantum computer, Nat. Commun. 11, 2963 (2020), arXiv:1905.09294.
https:/​/​doi.org/​10.1038/​s41467-020-16790-9
arXiv:1905.09294

[14] F. Mintert and C. Wunderlich, Ion-trap quantum logic using long-wavelength radiation, Phys. Rev. Lett. 87, 257904 (2001), arXiv:quant-ph/​0104041.
https:/​/​doi.org/​10.1103/​PhysRevLett.87.257904
arXiv:quant-ph/0104041

[15] C. Wunderlich, Conditional spin resonance with trapped ions, in Laser Physics at the Limits, edited by H. Figger, C. Zimmermann, and D. Meschede (Springer, 2002) pp. 261–273, arXiv:quant-ph/​0111158.
https:/​/​doi.org/​10.1007/​978-3-662-04897-9_25
arXiv:quant-ph/0111158

[16] N. Timoney, I. Baumgart, M. Johanning, A. F. Varon, C. Wunderlich, M. B. Plenio, and A. Retzker, Quantum Gates and Memory using Microwave Dressed States, Nature 476, 185 (2011), arXiv:1105.1146.
https:/​/​doi.org/​10.1038/​nature10319
arXiv:1105.1146

[17] C. Ospelkaus, U. Warring, Y. Colombe, K. R. Brown, J. M. Amini, D. Leibfried, and D. J. Wineland, Microwave quantum logic gates for trapped ions, Nature 476, 181 (2011), arXiv:1104.3573.
https:/​/​doi.org/​10.1038/​nature10290
arXiv:1104.3573

[18] A. Khromova, C. Piltz, B. Scharfenberger, T. Gloger, M. Johanning, A. Varón, and C. Wunderlich, Designer spin pseudomolecule implemented with trapped ions in a magnetic gradient, Phys. Rev. Lett. 108, 220502 (2012), arXiv:1112.5302.
https:/​/​doi.org/​10.1103/​PhysRevLett.108.220502
arXiv:1112.5302

[19] C. Piltz, T. Sriarunothai, S. S. Ivanov, S. Wölk, and C. Wunderlich, Versatile microwave-driven trapped ion spin system for quantum information processing, Sci. Adv. 2, e1600093 (2016), arXiv:1509.01478.
https:/​/​doi.org/​10.1126/​sciadv.1600093
arXiv:1509.01478

[20] B. Lekitsch, S. Weidt, A. G. Fowler, K. Mølmer, S. J. Devitt, C. Wunderlich, and W. K. Hensinger, Blueprint for a microwave trapped-ion quantum computer, Sci. Adv. 3, e1601540 (2017), arXiv:1508.00420.
https:/​/​doi.org/​10.1126/​sciadv.1601540
arXiv:1508.00420

[21] S. Wölk and C. Wunderlich, Quantum dynamics of trapped ions in a dynamic field gradient using dressed states, New J. Phys. 19, 083021 (2017), arXiv:1606.04821.
https:/​/​doi.org/​10.1088/​1367-2630/​aa7b22
arXiv:1606.04821

[22] J. Cohn, M. Motta, and R. M. Parrish, Quantum filter diagonalization with compressed double-factorized Hamiltonians, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040352
arXiv:2104.08957

[23] A. Sørensen and K. Mølmer, Spin-spin interaction and spin squeezing in an optical lattice, Phys. Rev. Lett. 83, 2274 (1999), arXiv:quant-ph/​9903044.
https:/​/​doi.org/​10.1103/​PhysRevLett.83.2274
arXiv:quant-ph/9903044

[24] A. Sørensen and K. Mølmer, Entanglement and quantum computation with ions in thermal motion, Phys. Rev. A 62, 022311 (2000), arXiv:quant-ph/​0002024.
https:/​/​doi.org/​10.1103/​PhysRevA.62.022311
arXiv:quant-ph/0002024

[25] T. Choi, S. Debnath, T. A. Manning, C. Figgatt, Z. X. Gong, L. M. Duan, and C. Monroe, Optimal quantum control of multimode couplings between trapped ion qubits for scalable entanglement, Phys. Rev. Lett. 112, 190502 (2014), arXiv:1401.1575.
https:/​/​doi.org/​10.1103/​PhysRevLett.112.190502
arXiv:1401.1575

[26] A. Parra-Rodriguez, P. Lougovski, L. Lamata, E. Solano, and M. Sanz, Digital-analog quantum computation, Phys. Rev. A 101, 022305 (2020), arXiv:1812.03637.
https:/​/​doi.org/​10.1103/​PhysRevA.101.022305
arXiv:1812.03637

[27] D. Maslov and B. Zindorf, Depth optimization of CZ, CNOT, and Clifford circuits, IEEE Transactions on Quantum Engineering 3, 1 (2022), arXiv:2201.05215.
https:/​/​doi.org/​10.1109/​TQE.2022.3180900
arXiv:2201.05215

[28] S. S. Ivanov, M. Johanning, and C. Wunderlich, Simplified implementation of the quantum Fourier transform with Ising-type Hamiltonians: Example with ion traps, arXiv:1503.08806 (2015).
arXiv:1503.08806

[29] G. Breit and I. I. Rabi, Measurement of nuclear spin, Phys. Rev. 38, 2082 (1931).
https:/​/​doi.org/​10.1103/​PhysRev.38.2082.2

[30] S. Bourdeauducq, whitequark, R. Jördens, D. Nadlinger, Y. Sionneau, and F. Kermarrec, ARTIQ 10.5281/​zenodo.6619071 (2021), Version 6.
https:/​/​doi.org/​10.5281/​zenodo.6619071

[31] I. Dumer, D. Micciancio, and M. Sudan, Hardness of approximating the minimum distance of a linear code, IEEE Trans. Inf. Theory 49, 22 (2003).
https:/​/​doi.org/​10.1109/​TIT.2002.806118

[32] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Tech. Rep. (Defense Technical Information Center, 1976).
https:/​/​apps.dtic.mil/​sti/​citations/​ADA025602

[33] H. Karloff, Linear Programming (Birkhäuser Boston, 1991) pp. 23–47.
https:/​/​doi.org/​10.1007/​978-0-8176-4844-2_2

[34] M. Kliesch and I. Roth, Theory of quantum system certification, PRX Quantum 2, 010201 (2021), tutorial, arXiv:2010.05925.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010201
arXiv:2010.05925

[35] N. B. Karahanoğlu, H. Erdoğan, and Ş. İ. Birbil, A mixed integer linear programming formulation for the sparse recovery problem in compressed sensing, in 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (2013) pp. 5870–5874.
https:/​/​doi.org/​10.1109/​ICASSP.2013.6638790

[36] M. Johanning, A. F. Varón, and C. Wunderlich, Quantum simulations with cold trapped ions, J. Phys. B 42, 154009 (2009), arXiv:0905.0118.
https:/​/​doi.org/​10.1088/​0953-4075/​42/​15/​154009
arXiv:0905.0118

[37] P. Baßler and M. Zipper, Source code for ``Synthesis of and compilation with time-optimal multi-qubit gates'', https:/​/​github.com/​matt-zipp/​arXiv-2206.06387 (2022).
https:/​/​github.com/​matt-zipp/​arXiv-2206.06387

[38] S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res. 17, 1 (2016).
http:/​/​jmlr.org/​papers/​v17/​15-408.html

[39] A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd, A rewriting system for convex optimization problems, J. Control Decis. 5, 42 (2018), arXiv:1709.04494.
https:/​/​doi.org/​10.1080/​23307706.2017.1397554
arXiv:1709.04494

[40] Free Software Foundation, GLPK (GNU Linear Programming Kit) (2012), version: 0.4.6.
https:/​/​www.gnu.org/​software/​glpk/​

[41] MOSEK ApS, MOSEK Optimizer API for Python 9.3.14 (2022).
https:/​/​docs.mosek.com/​latest/​pythonapi/​index.html

[42] S. Kukita, H. Kiya, and Y. Kondo, Short composite quantum gate robust against two common systematic errors, J. Phys. Soc. Japan 91, 104001 (2022), arXiv:2112.12945.
https:/​/​doi.org/​10.7566/​JPSJ.91.104001
arXiv:2112.12945

[43] D. A. Spielman and S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https:/​/​doi.org/​10.1145/​990308.990310
arXiv:cs/0111050

[44] S. Bravyi and D. Maslov, Hadamard-free circuits expose the structure of the Clifford group, IEEE Trans. Inf. Theory 67, 4546 (2021), arXiv:2003.09412.
https:/​/​doi.org/​10.1109/​TIT.2021.3081415
arXiv:2003.09412

[45] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004), arXiv:quant-ph/​0406196.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328
arXiv:quant-ph/0406196

[46] D. Maslov and M. Roetteler, Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations, IEEE Trans. Inf. Theory 64, 4729 (2018), arXiv:1705.09176.
https:/​/​doi.org/​10.1109/​TIT.2018.2825602
arXiv:1705.09176

[47] R. Duncan, A. Kissinger, S. Perdrix, and J. van de Wetering, Graph-theoretic simplification of quantum circuits with the ZX-calculus, Quantum 4, 279 (2020), arXiv:1902.03178.
https:/​/​doi.org/​10.22331/​q-2020-06-04-279
arXiv:1902.03178

[48] R. Kueng and D. Gross, Qubit stabilizer states are complex projective 3-designs, arXiv:1510.02767.
arXiv:1510.02767

[49] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nat. Phys. 16, 1050 (2020), arXiv:2002.08953.
https:/​/​doi.org/​10.1038/​s41567-020-0932-7
arXiv:2002.08953

[50] D. Schlingemann, Stabilizer codes can be realized as graph codes, arXiv:quant-ph/​0111080 (2001).
arXiv:quant-ph/0111080

[51] D. Schlingemann and R. F. Werner, Quantum error-correcting codes associated with graphs, Phys. Rev. A 65, 012308 (2001), arXiv:quant-ph/​0012111.
https:/​/​doi.org/​10.1103/​PhysRevA.65.012308
arXiv:quant-ph/0012111

[52] V. Kliuchnikov, K. Lauter, R. Minko, A. Paetznick, and C. Petit, Shorter quantum circuits, arXiv:2203.10064 (2022).
arXiv:2203.10064

[53] M. Born and R. Oppenheimer, Zur Quantentheorie der Molekeln, Ann. Phys. 389, 457 (1927).
https:/​/​doi.org/​10.1002/​andp.19273892002

[54] J. Kempe, A. Kitaev, and O. Regev, The complexity of the local Hamiltonian problem, SIAM J. Comput. 35, 1070 (2006), arXiv:quant-ph/​0406180.
https:/​/​doi.org/​10.1137/​S0097539704445226
arXiv:quant-ph/0406180

[55] R. M. Parrish and P. L. McMahon, Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation, arXiv:1909.08925 (2019).
arXiv:1909.08925

[56] K. Klymko, C. Mejuto-Zaera, S. J. Cotton, F. Wudarski, M. Urbanek, D. Hait, M. Head-Gordon, K. B. Whaley, J. Moussa, N. Wiebe, W. A. de Jong, and N. M. Tubman, Real time evolution for ultracompact Hamiltonian eigenstates on quantum hardware, PRX Quantum 3, 020323 (2022), arXiv:2103.08563.
https:/​/​doi.org/​10.1103/​PRXQuantum.3.020323
arXiv:2103.08563

[57] N. H. Stair, R. Huang, and F. A. Evangelista, A multireference quantum Krylov algorithm for strongly correlated electrons, J. Chem. Theory Comput. 16, 2236 (2020), pMID: 32091895.
https:/​/​doi.org/​10.1021/​acs.jctc.9b01125

[58] V. Kliuchnikov, D. Maslov, and M. Mosca, Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates, Quantum Inform. Comput. 13, 607 (2013), arXiv:1206.5236.
https:/​/​doi.org/​10.26421/​QIC13.7-8-4
arXiv:1206.5236

[59] N. J. Ross and P. Selinger, Optimal ancilla-free Clifford+T approximation of z-rotations, Quantum Inform. Compu. 16, 901 (2016), arXiv:1403.2975.
https:/​/​doi.org/​10.26421/​QIC16.11-12-1
arXiv:1403.2975

[60] A. Bouland and T. Giurgica-Tiron, Efficient universal quantum compilation: An inverse-free Solovay-Kitaev algorithm, arXiv:2112.02040.
arXiv:2112.02040

[61] M. Amy, P. Azimzadeh, and M. Mosca, On the CNOT-complexity of CNOT-PHASE circuits, Quantum Sci. Technol. 4, 015002 (2018), arXiv:1712.01859.
https:/​/​doi.org/​10.1088/​2058-9565/​aad8ca
arXiv:1712.01859

[62] M. Amy, D. Maslov, and M. Mosca, Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 33, 1476 (2014), arXiv:1303.2042.
https:/​/​doi.org/​10.1109/​TCAD.2014.2341953
arXiv:1303.2042

[63] R. O'Donnell, Analysis of Boolean Functions (Cambridge University Press) arXiv:2105.10386.
arXiv:2105.10386
https:/​/​www.cambridge.org/​core/​books/​analysis-of-boolean-functions/​B05A66E4DCC778E02B84C16376F4D1FD

[64] G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large-scale traveling-salesman problem, Operations Research Society of America 2, 393 (1954).
https:/​/​doi.org/​10.1287/​opre.2.4.393

[65] P. García-Molina, A. Martin, and M. Sanz, Noise in digital and digital-analog quantum computation, arXiv:2107.12969.
arXiv:2107.12969

[66] P. T. Fisk, M. J. Sellars, M. A. Lawn, and G. Coles, Accurate measurement of the 12.6 GHz ``clock'' transition in trapped $^{171}$Yb$^+$ ions, IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control 44, 344 (1997).
https:/​/​doi.org/​10.1109/​58.585119

[67] S. F. D. Waldron, An Introduction to Finite Tight Frames, Applied and Numerical Harmonic Analysis (Springer New York, New York, NY, 2018).
https:/​/​doi.org/​10.1007/​978-0-8176-4815-2

[68] R. B. Holmes and V. I. Paulsen, Optimal frames for erasures, Linear Algebra Its Appl. 377, 31 (2004).
https:/​/​doi.org/​10.1016/​j.laa.2003.07.012

Cited by

[1] Mikel Garcia-de-Andoin, Álvaro Saiz, Pedro Pérez-Fernández, Lucas Lamata, Izaskun Oregi, and Mikel Sanz, "Digital-analog quantum computation with arbitrary two-body Hamiltonians", Physical Review Research 6 1, 013280 (2024).

[2] Pascal Baßler, Markus Heinrich, and Martin Kliesch, "Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds", Quantum 8, 1279 (2024).

[3] Anette Messinger, Michael Fellner, and Wolfgang Lechner, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 120 (2023) ISBN:979-8-3503-4323-6.

[4] Daniele Cuomo, "Architectures and circuits for distributed quantum computing", arXiv:2307.07908, (2023).

[5] Sergey Bravyi, Dmitri Maslov, and Yunseong Nam, "Constant-Cost Implementations of Clifford Operations and Multiply-Controlled Gates Using Global Interactions", Physical Review Letters 129 23, 230501 (2022).

[6] Anette Messinger, Michael Fellner, and Wolfgang Lechner, "Constant Depth Code Deformations in the Parity Architecture", arXiv:2303.08602, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-19 01:54:24) and SAO/NASA ADS (last updated successfully 2024-04-19 01:54:25). The list may be incomplete as not all publishers provide suitable and complete citation data.