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 (8)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Primitive Quantum Gates for Dihedral Gauge Theories
• Diagonal quantum circuits: their computational power and applications
• 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