Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds

Pascal Baßler1, Markus Heinrich1, and Martin Kliesch2

1Institute for Theoretical Physics, Heinrich Heine University Düsseldorf, Germany
2Institute for Quantum Inspired and Quantum Optimization, Hamburg University of Technology, Germany

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


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($n$) for $n$ 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.

► BibTeX data

► References

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

[2] 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.

[3] M. Kjaergaard, M. E. Schwartz, J. Braumüller, 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.

[4] 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.

[5] 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.

[6] P. Baßler, 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.

[7] F. Barahona and A. R. Mahjoub, On the cut polytope, Mathematical Programming 36, 157 (1986).

[8] M. R. Garey and D. S. Johnson, Computers and intractability, Vol. 29 (W. H. Freeman and Company, New York, 2002).

[9] 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.

[10] 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).

[11] 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.

[12] 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.

[13] D. Maslov and B. Zindorf, Depth optimization of CZ, CNOT, and Clifford circuits, IEEE Transactions on Quantum Engineering 3, 1 (2022), arxiv:2201.05215.

[14] S. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press, 2009).

[15] E. Rich, The problem classes FP and FNP, in Automata, Computability and Complexity: Theory and Applications (Pearson Education, 2007) pp. 510–511.

[16] M. Johanning, Isospaced linear ion strings, Appl. Phys. B 122, 71 (2016).

[17] M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope, Linear Algebra and its Applications 223-224, 439 (1995).

[18] M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, 1st ed., Algorithms and Combinatorics (Springer Berlin Heidelberg, 2009).

[19] 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.

[20] R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics 12, 311 (1933).

[21] A. Hedayat and W. D. Wallis, Hadamard matrices and their applications, The Annals of Statistics 6, 1184 (1978).

[22] H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, Journal of Combinatorial Designs 13, 435 (2005).

[23] D. Ž. Đoković, 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.

[24] J. Cohn, M. Motta, and R. M. Parrish, Quantum filter diagonalization with compressed double-factorized Hamiltonians, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.

[25] 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.

[26] S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res. 17, 1 (2016), arXiv:1603.00943.

[27] 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.

[28] Free Software Foundation, GLPK (GNU Linear Programming Kit) (2012), version: 0.4.6.

[29] A. T. Phillips and J. B. Rosen, A parallel algorithm for constrained concave quadratic global minimization, Mathematical Programming 42, 421 (1988).

[30] M. Dür, R. Horst, and M. Locatelli, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications 217, 637 (1998).

[31] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear programming: theory and algorithms, 3rd edition (John wiley & sons, 2013).

[32] M. A. Hanson, Invexity and the Kuhn–Tucker Theorem, Journal of Mathematical Analysis and Applications 236, 594 (1999).

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-04-12 13:41:31). On SAO/NASA ADS no data on citing works was found (last attempt 2024-04-12 13:41:31).