{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T01:52:08Z","timestamp":1780537928181,"version":"3.54.1"},"reference-count":32,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"German Federal Ministry of Education and Research","award":["13N15522"],"award-info":[{"award-number":["13N15522"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Multi-qubit entangling interactions arise naturally in several quantum computing platforms and promise advantages over traditional two-qubit gates. In particular, a fixed multi-qubit Ising-type interaction together with single-qubit X-gates can be used to synthesize global ZZ-gates (GZZ gates). In this work, we first show that the synthesis of such quantum gates that are time-optimal is NP-hard. Second, we provide explicit constructions of special time-optimal multi-qubit gates. They have constant gate times and can be implemented with linearly many X-gate layers. Third, we develop a heuristic algorithm with polynomial runtime for synthesizing fast multi-qubit gates. Fourth, we derive lower and upper bounds on the optimal GZZ gate-time. Based on explicit constructions of GZZ gates and numerical studies, we conjecture that any GZZ gate can be executed in a time O(<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>) for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> qubits. Our heuristic synthesis algorithm leads to GZZ gate-times with a similar scaling, which is optimal in this sense. We expect that our efficient synthesis of fast multi-qubit gates allows for faster and, hence, also more error-robust execution of quantum algorithms.<\/jats:p>","DOI":"10.22331\/q-2024-03-13-1279","type":"journal-article","created":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:06:50Z","timestamp":1710335210000},"page":"1279","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds"],"prefix":"10.22331","volume":"8","author":[{"given":"Pascal","family":"Ba\u00dfler","sequence":"first","affiliation":[{"name":"Institute for Theoretical Physics, Heinrich Heine University D\u00fcsseldorf, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Markus","family":"Heinrich","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Heinrich Heine University D\u00fcsseldorf, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Kliesch","sequence":"additional","affiliation":[{"name":"Institute for Quantum Inspired and Quantum Optimization, Hamburg University of Technology, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"X. Wang, A. S\u00f8rensen, and K. M\u00f8lmer, Multibit gates for quantum computing, Phys. Rev. Lett. 86, 3907 (2001), arXiv:quant-ph\/0012055.","DOI":"10.1103\/PhysRevLett.86.3907"},{"key":"1","doi-asserted-by":"publisher","unstructured":"T. Monz, P. Schindler, J. T. Barreiro, M. Chwalla, D. Nigg, W. A. Coish, M. Harlander, W. H\u00e4nsel, M. Hennrich, and R. Blatt, 14-qubit entanglement: Creation and coherence, Phys. Rev. Lett. 106, 130506 (2011), arXiv:1009.6126.","DOI":"10.1103\/PhysRevLett.106.130506"},{"key":"2","doi-asserted-by":"publisher","unstructured":"M. Kjaergaard, M. E. Schwartz, J. Braum\u00fcller, P. Krantz, J. I.-J. Wang, S. Gustavsson, and W. D. Oliver, Superconducting qubits: Current state of play, Annual Review of Condensed Matter Physics 11, 369 (2020), arXiv:1905.13641.","DOI":"10.1146\/annurev-conmatphys-031119-050605"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41586-019-1427-5"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Y. Lu, S. Zhang, K. Zhang, W. Chen, Y. Shen, J. Zhang, J.-N. Zhang, and K. Kim, Scalable global entangling gates on arbitrary ion qubits, Nature 572, 363 (2019), arXiv:1901.03508.","DOI":"10.1038\/s41586-019-1428-4"},{"key":"5","doi-asserted-by":"publisher","unstructured":"P. Ba\u00dfler, M. Zipper, C. Cedzich, M. Heinrich, P. H. Huber, M. Johanning, and M. Kliesch, Synthesis of and compilation with time-optimal multi-qubit gates, Quantum 7, 984 (2023), arXiv:2206.06387.","DOI":"10.22331\/q-2023-04-20-984"},{"key":"6","doi-asserted-by":"publisher","unstructured":"F. Barahona and A. R. Mahjoub, On the cut polytope, Mathematical Programming 36, 157 (1986).","DOI":"10.1007\/BF02592023"},{"key":"7","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability, Vol. 29 (W. H. Freeman and Company, New York, 2002)."},{"key":"8","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations, Phys. Rev. Lett. 117, 080501 (2016), arXiv:1504.07999.","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"9","unstructured":"J. Allcock, J. Bao, J. F. Doriguello, A. Luongo, and M. Santha, Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits, arXiv:2308.08539 (2023)."},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.129.230501"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/TIT.2021.3081415"},{"key":"12","doi-asserted-by":"publisher","unstructured":"D. Maslov and B. Zindorf, Depth optimization of CZ, CNOT, and Clifford circuits, IEEE Transactions on Quantum Engineering 3, 1 (2022), arxiv:2201.05215.","DOI":"10.1109\/TQE.2022.3180900"},{"key":"13","unstructured":"S. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press, 2009)."},{"key":"14","unstructured":"E. Rich, The problem classes FP and FNP, in Automata, Computability and Complexity: Theory and Applications (Pearson Education, 2007) pp. 510\u2013511."},{"key":"15","doi-asserted-by":"publisher","unstructured":"M. Johanning, Isospaced linear ion strings, Appl. Phys. B 122, 71 (2016).","DOI":"10.1007\/s00340-016-6340-0"},{"key":"16","doi-asserted-by":"publisher","unstructured":"M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope, Linear Algebra and its Applications 223-224, 439 (1995).","DOI":"10.1016\/0024-3795(95)00271-R"},{"key":"17","doi-asserted-by":"publisher","unstructured":"M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, 1st ed., Algorithms and Combinatorics (Springer Berlin Heidelberg, 2009).","DOI":"10.1007\/978-3-642-04295-9"},{"key":"18","doi-asserted-by":"publisher","unstructured":"M. E.-Nagy, M. Laurent, and A. Varvitsiotis, Complexity of the positive semidefinite matrix completion problem with a rank constraint, Springer International Publishing , 105 (2013), arXiv:1203.6602.","DOI":"10.1007\/978-3-319-00200-2_7"},{"key":"19","doi-asserted-by":"publisher","unstructured":"R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics 12, 311 (1933).","DOI":"10.1002\/sapm1933121311"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. Hedayat and W. D. Wallis, Hadamard matrices and their applications, The Annals of Statistics 6, 1184 (1978).","DOI":"10.1214\/aos\/1176344370"},{"key":"21","doi-asserted-by":"publisher","unstructured":"H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, Journal of Combinatorial Designs 13, 435 (2005).","DOI":"10.1002\/jcd.20043"},{"key":"22","doi-asserted-by":"publisher","unstructured":"D. \u017d. \u0110okovi\u0107, O. Golubitsky, and I. S. Kotsireas, Some new orders of Hadamard and Skew-Hadamard matrices, Journal of Combinatorial Designs 22, 270 (2014), arXiv:1301.3671.","DOI":"10.1002\/jcd.21358"},{"key":"23","doi-asserted-by":"publisher","unstructured":"J. Cohn, M. Motta, and R. M. Parrish, Quantum filter diagonalization with compressed double-factorized Hamiltonians, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.","DOI":"10.1103\/PRXQuantum.2.040352"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/990308.990310"},{"key":"25","unstructured":"S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res. 17, 1 (2016), arXiv:1603.00943."},{"key":"26","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1080\/23307706.2017.1397554"},{"key":"27","unstructured":"Free Software Foundation, GLPK (GNU Linear Programming Kit) (2012), version: 0.4.6."},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. T. Phillips and J. B. Rosen, A parallel algorithm for constrained concave quadratic global minimization, Mathematical Programming 42, 421 (1988).","DOI":"10.1007\/BF01589415"},{"key":"29","doi-asserted-by":"publisher","unstructured":"M. D\u00fcr, R. Horst, and M. Locatelli, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications 217, 637 (1998).","DOI":"10.1006\/jmaa.1997.5745"},{"key":"30","doi-asserted-by":"publisher","unstructured":"M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear programming: theory and algorithms, 3rd edition (John wiley & sons, 2013).","DOI":"10.1002\/0471787779"},{"key":"31","doi-asserted-by":"publisher","unstructured":"M. A. Hanson, Invexity and the Kuhn\u2013Tucker Theorem, Journal of Mathematical Analysis and Applications 236, 594 (1999).","DOI":"10.1006\/jmaa.1999.6484"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-03-13-1279\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:06:58Z","timestamp":1710335218000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-03-13-1279\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":32,"URL":"https:\/\/doi.org\/10.22331\/q-2024-03-13-1279","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"article-number":"1279"}}