Time complexity and gate complexity of the quantum Fourier transform

Thomas Schulte‐Herbrüggen, Andreas K. Spörl, Navin Khaneja +1 more

In this paper, we demonstrate how optimal control methods can be used to speed up the implementation of modules of quantum algorithms or quantum simulations in networks of coupled qubits. The gain is most prominent in realistic cases, where the qubits are not all mutually coupled. Thus the shortest times obtained depend on the coupling topology as well as on the characteristic ratio of the time scales for local controls vs nonlocal (i.e., coupling) evolutions in the specific experimental setting. Relating these minimal times to the number of qubits gives the tightest known upper bounds to the actual time complexity of the quantum modules. As will be shown, time complexity is a more realistic measure of the experimental cost than the usual gate complexity. In the limit of fast local controls (as, e.g., in NMR), time-optimized realizations are shown for the quantum Fourier transform (QFT) and the multiply controlled NOT gate $({\mathrm{C}}^{n\ensuremath{-}1}\mathrm{NOT})$ in various coupling topologies of $n$ qubits. The speed-ups are substantial: in a chain of six qubits the quantum Fourier transform so far obtained by optimal control is more than eight times faster than the standard decomposition into controlled phase, Hadamard and SWAP gates, while the ${\mathrm{C}}^{n\ensuremath{-}1}\mathrm{NOT}$ gate for a completely coupled network of six qubits is nearly seven times faster.

Umesh V. Vazirani

이두영

Norihito Higa, Mitsunaga Kinjo

In this study, we design small-scale circuit as quantum Fourier transform gate emulator which is a part of prime factorization quantum algorithm (Shor's algorithm), based on previous proposed quantum logic gate emulator with complex probability amplitude.

S. S. Zhou, T. Loke, Josh Izaac +1 more

Valerii Hlukhov

Quantum computers are analog and probabilistic computers and, in fact, they play the role of coprocessors in relation to classical computers. The components of quantum coprocessors are called qubits. Their behavior should be described by a wave function. In particular, qubits can be discrete objects - finite states machines. Such qubits will be called digital. Quantum coprocessors and quantum computers built on their basis will also be called digital. External influences on digital qubits are fed through digital quantum gates. So a digital qubit is a unique chain of digital quantum gates. Digital quantum coprocessor can be implemented in FPGA as several chains of digital quantum.The article explores FPGA-based digital quantum coprocessor. It consists of 32 qubits. The structures of digital quantum gates, digital qubits, and a digital quantum coprocessor capable of performing the quantum Fourier transform are presented. Digital qubits were implemented for the case of real amplitudes of the wave functions.The results of the quantum Fourier transform of a 32-qubit digital quantum coprocessor implemented on one FPGA are presented.The execution time of one quantum Fourier transform does not depend on the number of qubits in the digital quantum coprocessor and is commensurate with the time of electron spin change (near 10 ns). But the time complexity of the quantum Fourier transform is probabilistic polynomial in time. The measured ratio of correct results for a 32-qubit coprocessor is approximately 1700 ppm.