Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count

Abstract

Current noisy intermediate-scale quantum (NISQ) devices can only execute small circuits with shallow depth, as they are still constrained by the presence of noise: quantum gates have error rates and quantum states are fragile due to decoherence. Hence, it is of great importance to optimize the depth/gate-count when designing quantum circuits for specific tasks. Diagonal unitary matrices are well-known to be key building blocks of many quantum algorithms or quantum computing procedures. Prior work has discussed the synthesis of diagonal unitary matrices over the primitive gate set $\{\text{CNOT},R_Z\}$. However, the problem has not yet been fully understood, since the existing synthesis methods have not optimized the circuit depth. In this paper, we propose a depth-optimized synthesis algorithm that automatically produces a quantum circuit for any given diagonal unitary matrix. Specially, it not only ensures the asymptotically optimal gate-count, but also nearly halves the total circuit depth compared with the previous method. Technically, we discover a uniform circuit rewriting rule well-suited for reducing the circuit depth. The performance of our synthesis algorithm is both theoretically analyzed and experimentally validated by evaluations on two examples. First, we achieve a nearly 50\% depth reduction over Welch's method for synthesizing random diagonal unitary matrices with up to 16 qubits. Second, we achieve an average of 22.05\% depth reduction for resynthesizing the diagonal part of specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.

References in corpus (25)

• Elementary gates for quantum computation
• Noisy intermediate-scale quantum (NISQ) algorithms
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Grover Algorithm with zero theoretical failure rate
• Quantum advantage with shallow circuits
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Quantum Circuits for General Multiqubit Gates
• Synthesis and Optimization of Reversible Circuits - A Survey
• Minimal Universal Two-qubit Quantum Circuits
• Efficient decomposition of quantum gates
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Automated optimization of large quantum circuits with continuous parameters
• Parallel Entangling Operations on a Universal Ion Trap Quantum Computer
• Quantum circuits with uniformly controlled one-qubit gates
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Quantum circuit optimizations for NISQ architectures
• Two-qubit entangling gates within arbitrarily long chains of trapped ions
• Primitive Quantum Gates for Dihedral Gauge Theories
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Generating a state $t$-design by diagonal quantum circuits
• Diagonal quantum circuits: their computational power and applications
• Parallelizing quantum circuit synthesis
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Quantum algorithm for learning secret strings and its experimental demonstration

Cited by in corpus (3)

• Approximate real-time evolution operator for potential with one ancillary qubit and application to first-quantized Hamiltonian simulation
• Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique
• Optimizing Quantum Transformation Matrices: A Block Decomposition Approach for Efficient Gate Reduction