Time-optimal Multi-qubit Gates: Complexity, Efficient Heuristic And Gate-time Bounds

Republished By Plato

Followers: 0

Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Pascal Baßler¹, Markus Heinrich¹, and Martin Kliesch²

¹Institute for Theoretical Physics, Heinrich Heine University Düsseldorf, Germany
²Institute 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.

Abstract

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

@article{Bassler2024timeoptimalmulti, doi = {10.22331/q-2024-03-13-1279}, url = {https://doi.org/10.22331/q-2024-03-13-1279}, title = {Time-optimal multi-qubit gates: {C}omplexity, efficient heuristic and gate-time bounds}, author = {Ba{ss{}}ler, Pascal and Heinrich, Markus and Kliesch, Martin}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1279}, month = mar, year = {2024} }

► 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.
https://doi.org/10.1103/PhysRevLett.86.3907
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.
https://doi.org/10.1103/PhysRevLett.106.130506
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.
https://doi.org/10.1146/annurev-conmatphys-031119-050605
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.
https://doi.org/10.1038/s41586-019-1427-5
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.
https://doi.org/10.1038/s41586-019-1428-4
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.
https://doi.org/10.22331/q-2023-04-20-984
arXiv:2206.06387

[7] F. Barahona and A. R. Mahjoub, On the cut polytope, Mathematical Programming 36, 157 (1986).
https://doi.org/10.1007/BF02592023

[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.
https://doi.org/10.1103/PhysRevLett.117.080501
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).
arXiv:2308.08539

[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.
https://doi.org/10.1103/PhysRevLett.129.230501
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.
https://doi.org/10.1109/TIT.2021.3081415
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.
https://doi.org/10.1109/TQE.2022.3180900
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.
https://www.cs.utexas.edu/~ear/cs341/automatabook/AutomataTheoryBook.pdf

[16] M. Johanning, Isospaced linear ion strings, Appl. Phys. B 122, 71 (2016).
https://doi.org/10.1007/s00340-016-6340-0

[17] M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope, Linear Algebra and its Applications 223-224, 439 (1995).
https://doi.org/10.1016/0024-3795(95)00271-R

[18] M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, 1st ed., Algorithms and Combinatorics (Springer Berlin Heidelberg, 2009).
https://doi.org/10.1007/978-3-642-04295-9

[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.
https://doi.org/10.1007/978-3-319-00200-2_7
arXiv:1203.6602

[20] R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics 12, 311 (1933).
https://doi.org/10.1002/sapm1933121311

[21] A. Hedayat and W. D. Wallis, Hadamard matrices and their applications, The Annals of Statistics 6, 1184 (1978).
https://doi.org/10.1214/aos/1176344370

[22] H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, Journal of Combinatorial Designs 13, 435 (2005).
https://doi.org/10.1002/jcd.20043

[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.
https://doi.org/10.1002/jcd.21358
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.
https://doi.org/10.1103/PRXQuantum.2.040352
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.
https://doi.org/10.1145/990308.990310
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.
arXiv:1603.00943
http://jmlr.org/papers/v17/15-408.html

[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.
https://doi.org/10.1080/23307706.2017.1397554
arXiv:1709.04494

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

[29] A. T. Phillips and J. B. Rosen, A parallel algorithm for constrained concave quadratic global minimization, Mathematical Programming 42, 421 (1988).
https://doi.org/10.1007/BF01589415

[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).
https://doi.org/10.1006/jmaa.1997.5745

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

[32] M. A. Hanson, Invexity and the Kuhn–Tucker Theorem, Journal of Mathematical Analysis and Applications 236, 594 (1999).
https://doi.org/10.1006/jmaa.1999.6484

Cited by

Could not fetch Crossref cited-by data during last attempt 2024-03-13 13:00:52: Could not fetch cited-by data for 10.22331/q-2024-03-13-1279 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2024-03-13 13:00:52).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-03-13-1279/

Time Stamp: March 13, 2024

Time Stamp: Feb 2, 2023

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

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

Counting stabiliser codes for arbitrary dimension

Sequential hypothesis testing for continuously-monitored quantum systems

Fast simulation of planar Clifford circuits

Fully non-positive-partial-transpose genuinely entangled subspaces

Design of quantum optical experiments with logic artificial intelligence

Geometric Operator Quantum Speed Limit, Wegner Hamiltonian Flow and Operator Growth

Time-marching based quantum solvers for time-dependent linear differential equations

Effective versus Floquet theory for the Kerr parametric oscillator

Model predictive control for robust quantum state preparation

Here comes the SU(N): multivariate quantum gates and gradients

Fast quantum transfer mediated by topological domain walls

Probing sign structure using measurement-induced entanglement

About Us

Vertical Search & Ai

Platform

Stay Connected

Account