Quantum circuit unoptimization - Yusei Mori; Hideaki Hakoshima; Kyohei Sudo; Toshio Mori; Kosuke Mitarai; Keisuke Fujii (Physical Review Research)
Optimization of circuits is an essential task for both quantum and classical computers to improve their efficiency. In contrast, classical logic optimization is known to be difficult, and a lot of heuristic approaches have been developed so far. In this paper, we define and construct a quantum algorithmic primitive called quantum circuit unoptimization, which makes a given quantum circuit complex by introducing some redundancies while preserving circuit equivalence, i.e., the inverse operation of circuit optimization. Using quantum circuit unoptimization, we propose the quantum circuit equivalence test, a decision problem contained both in NP and BQP classes, but is not trivially included in the P class. Furthermore, as a practical application, we construct concrete unoptimization recipes to generate compiler benchmarks and evaluate circuit optimization performance using Qiskit and Pytket. Our numerical simulations demonstrate that the quantum circuit unoptimizer systematically generates redundant circuits that are challenging for compilers to optimize, which can be used to compare the performance of different compilers and improve them. We also offer potential applications of quantum circuit unoptimization, such as generating quantum advantageous machine learning data sets and quantum computer fidelity benchmarks.