Optimizing Gate Decomposition for High-Level Quantum Programming

Abstract

This paper presents novel methods for optimizing multi-controlled quantum gates, which naturally arise in high-level quantum programming. Our primary approach involves rewriting $U(2)$ gates as $SU(2)$ gates, utilizing one auxiliary qubit for phase correction. This reduces the number of CNOT gates required to decompose any multi-controlled quantum gate from $O(n^2)$ to at most $32n$. Additionally, we can reduce the number of CNOTs for multi-controlled Pauli gates from $16n$ to $12n$ and propose an optimization to reduce the number of controlled gates in high-level quantum programming. We have implemented these optimizations in the Ket quantum programming platform and demonstrated significant reductions in the number of gates. For instance, for a Grover's algorithm layer with 114 qubits, we achieved a reduction in the number of CNOTs from 101,252 to 2,684. This reduction in the number of gates significantly impacts the execution time of quantum algorithms, thereby enhancing the feasibility of executing them on NISQ computers.

References in corpus (24)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Quantum computational advantage using photons
• Quantum Chemistry in the Age of Quantum Computing
• Superconducting Qubits: Current State of Play
• Strong quantum computational advantage using a superconducting quantum processor
• A >99.9%-fidelity quantum-dot spin qubit with coherence limited by charge noise
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Efficient Z-Gates for Quantum Computing
• Quantum computing with neutral atoms
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• ProjectQ: An Open Source Software Framework for Quantum Computing
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Quantum computing for finance
• Q#: Enabling scalable quantum computing and development with a high-level domain-specific language
• Quantum Circuits for Isometries
• Quantum computing with Qiskit
• The QICK (Quantum Instrumentation Control Kit): Readout and control for qubits and detectors
• Linear-depth quantum circuits for multiqubit controlled gates
• MQT QMAP: Efficient Quantum Circuit Mapping
• Wavefunction preparation and resampling using a quantum computer
• Simulating noisy quantum channels via quantum state preparation algorithms
• QSystem: bitwise representation for quantum circuit simulations

Cited by in corpus (4)

• Quantum circuits for partial differential equations in Fourier space
• Dynamics and computation in linear open quantum walks
• All You Need is pi: Quantum Computing with Hermitian Gates
• A Time Optimization Framework for the Implementation of Robust and Low-latency Quantum Circuits