Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm
- 1 October 2020
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)
Abstract
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems. The multi-qubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA-circuit. Consequently, the circuit-depth and cumulative gate-count become lower which is beneficial for circuit execution time and noise resilience. A less number of gates indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, finding the best-ordered circuit is a difficult problem and does not scale well with circuit size. This paper presents four generic methodologies to optimize QAOA-circuits by exploiting gate re-ordering. We demonstrate a reduction in gate-count by ≈23.0% and circuit-depth by ≈53.0% on average over a conventional approach without incurring any compilation-time penalty. We also present a variation-aware compilation which enhances the compiled circuit success probability by ≈62.7% for the target hardware over the variation unaware approach. A new metric, Approximation Ratio Gap (ARG), is proposed to validate the quality of the compiled QAOA-circuit instances on actual devices. Hardware implementation of a number of QAOA instances shows ≈25.8% improvement in the proposed metric on average over the conventional approach on ibmq 16 melbourne.Keywords
Funding Information
- National Science Foundation
This publication has 49 references indexed in Scilit:
- Wirebond crosstalk and cavity modes in large chip mounts for superconducting qubitsSuperconductor Science and Technology, 2011
- Randomized Benchmarking and Process Tomography for Gate Errors in a Solid-State QubitPhysical Review Letters, 2009
- Variational quantum approaches for computing vibrational energies of polyatomic moleculesMolecular Physics, 2008
- Initial Decoherence in Solid State QubitsPhysical Review Letters, 2005
- Multiple-particle interference and quantum error correctionProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1996
- Mixed-state entanglement and quantum error correctionPhysical Review A, 1996
- Quantum Error Correction for CommunicationPhysical Review Letters, 1996
- Error Correcting Codes in Quantum TheoryPhysical Review Letters, 1996
- Perfect Quantum Error Correcting CodePhysical Review Letters, 1996
- Scheme for reducing decoherence in quantum computer memoryPhysical Review A, 1995