Halving the cost of quantum multiplexed rotations

Abstract

We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls applying $n$ single-qubit arbitrary phase rotations from $4nb+\mathcal{O}(\sqrt{cnb})$ to $2nb+\mathcal{O}(\sqrt{cnb})$, and reduce the number of qubits needed by up to a factor of two. This generic quantum circuit primitive is found in many quantum algorithms, and our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations. We achieve this by extending recent ideas on stochastic compilation of quantum circuits to classical data and discuss space-time trade-offs and concentration of measure in its implementation.

arXiv comment9 pages

References in corpus (16)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Elucidating Reaction Mechanisms on Quantum Computers
• Synthesis of Quantum Logic Circuits
• Toward the first quantum simulation with quantum speedup
• Application of a resource theory for magic states to fault-tolerant quantum computing
• A random compiler for fast Hamiltonian simulation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• Quantum computing enhanced computational catalysis
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Solovay-Kitaev Decomposition Strategy for Single-Qubit Channels
• Shorter gate sequences for quantum computing by mixing unitaries
• Hybridized Methods for Quantum Simulation in the Interaction Picture