Baßler, PascalPascalBaßlerHeinrich, MarkusMarkusHeinrichKliesch, MartinMartinKliesch2023-11-102023-11-102023-07-20arXiv: 2307.11160 (2023)https://hdl.handle.net/11420/44119Multi-qubit interactions are omnipresent in quantum computing hardware, and they can generate multi-qubit entangling gates. Such gates promise advantages over traditional two-qubit gates. In this work, we focus on the quantum gate synthesis with multi-qubit Ising-type interactions and single-qubit gates. These interactions can generate global ZZ-gates (GZZ gates). We show that the synthesis of time-optimal multi-qubit gates is NP-hard. However, under certain assumptions we provide explicit constructions of time-optimal multi-qubit gates allowing for efficient synthesis. These constructed multi-qubit gates have a constant gate time and can be implemented with linear single-qubit gate layers. Moreover, a heuristic algorithm with polynomial runtime for synthesizing fast multi-qubit gates is provided. Finally, we prove lower and upper bounds on the optimal GZZ gate-time. Furthermore, we conjecture that any GZZ gate can be executed in a time O(n) for n qubits. We support this claim with theoretical and numerical results.enhttps://creativecommons.org/licenses/by/4.0/quant-phPhysicsPreprinthttps://doi.org/10.15480/882.1394510.48550/arXiv.2307.1116010.15480/882.139452307.11160v1Preprint