  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.
