Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions

Abstract

The standard circuit model for quantum computation presumes the ability to directly perform gates between arbitrary pairs of qubits, which is unlikely to be practical for large-scale experiments. Power-law interactions with strength decaying as $1/r^{\alpha }$ in the distance $r$ provide an experimentally realizable resource for information processing, whilst still retaining long-range connectivity. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. Our implementation allows the quantum Fourier transform (QFT) and Shor's algorithm to be performed on a $D$-dimensional lattice in time logarithmic in the number of qubits for interactions with $\alpha \le D$. As a corollary, we show that power-law systems with $\alpha \le D$ are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable. Complementarily, we develop a new technique to give a general lower bound, linear in the size of the system, on the time required to implement the QFT and the fanout gate in systems that are constrained by a linear light cone. This allows us to prove an asymptotically tighter lower bound for long-range systems than is possible with previously available techniques.

6 pages, 1 figure

References in corpus (14)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Experimental Comparison of Two Quantum Computing Architectures
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Alkaline-Earth-Metal Atoms as Few-Qubit Quantum Registers
• Strictly linear light cones in long-range interacting systems of arbitrary dimensions
• Hierarchy of linear light cones with long-range interactions
• The Lieb-Robinson light cone for power-law interactions
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Asymmetric blockade and multi-qubit gates via dipole-dipole interactions
• Absence of fast scrambling in thermodynamically stable long-range interacting systems
• Optimal State Transfer and Entanglement Generation in Power-law Interacting Systems
• Optimal Frobenius light cone in spin chains with power-law interactions
• Dipolar exchange induced transparency with Rydberg atoms