Tight speed limits on two-qubit gates in a fully-connected quantum computer*

A quantum computer with fully connected qubits is expected to perform quantum algorithms involving remote

quantum gates much faster than one with locally connected qubits. The exact amount of speedup is however

hard to quantify. Here we provide a strict upper bound of such speedup on an arbitrary two-qubit gate, for

an arbitrary number of qubits involved, and with an arbitrary time-dependent Hamiltonian containing strongly

long-range two-body interactions. The bound is tight up to a small prefactor. In addition, for an important

subclass of such Hamiltonians and SWAP gates, we obtain a bound that is quantitatively tight, the first of its

kind. This second bound is achieved via a newly developed Quantum Brachistochrone method that incorporates

inequality constraints. The bounds obtained here also pave the way towards obtaining tight Lieb-Robinson-type

bounds for strongly long-range interacting systems.