Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm
Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm
复制标题
DOI：
10.1109/micro50266.2020.00029
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
M. Alam;Abdullah Ash-Saki;Swaroop Ghosh
中科院分区：
文献类型：
--
作者：
M. Alam;Abdullah Ash-Saki;Swaroop Ghosh
量子近似优化算法（QAOA）是一种有望的量子 - 古典杂交算法，可以解决硬组合的优化问题。输出状态。此重新排序会导致更大的门和较少数量的额外交换门来编译QAOA电路。执行时间和噪声弹性。较少的门表明闸门的加速度较低，而降低的电路深度则意味着较小的量子量。通过电路大小，本文提出了四种通用方法，以利用门的重新排序来优化QAOA-CIRVITS。在任何汇编时，我们还提出了一个变化的汇编，该汇编将汇编的成功概率提高了目标硬件的62.7％。验证在实际设备上汇编的QAOA电路实例的质量。
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.