NISQ circuit compilation is the travelling salesman problem on a torus
Open Access
- 8 March 2021
- journal article
- research article
- Published by IOP Publishing in Quantum Science and Technology
- Vol. 6 (2), 025016
- https://doi.org/10.1088/2058-9565/abe665
Abstract
Noisy, intermediate-scale quantum (NISQ) computers are expected to execute quantum circuits of up to a few hundred qubits. The circuits have to conform to NISQ architectural constraints regarding qubit allocation and the execution of multi-qubit gates. Quantum circuit compilation (QCC) takes a nonconforming circuit and outputs a compatible circuit. Can classical optimisation methods be used for QCC? Compilation is a known combinatorial problem shown to be solvable by two types of operations: (1) qubit allocation, and (2) gate scheduling. We show informally that the two operations form a discrete ring. The search landscape of QCC is a two dimensional discrete torus where vertices represent configurations of how circuit qubits are allocated to NISQ registers. Torus edges are weighted by the cost of scheduling circuit gates. The novelty of our approach uses the fact that a circuit’s gate list is circular: compilation can start from any gate as long as all the gates will be processed, and the compiled circuit has the correct gate order. Our work bridges a theoretical and practical gap between classical circuit design automation and the emerging field of quantum circuit optimisation.This publication has 27 references indexed in Scilit:
- Compiling quantum circuits to realistic hardware architectures using temporal plannersQuantum Science and Technology, 2018
- Qubit allocationPublished by Association for Computing Machinery (ACM) ,2018
- Optimization of lattice surgery is NP-hardnpj Quantum Information, 2017
- Basic circuit compilation techniques for an ion-trap quantum machineNew Journal of Physics, 2017
- Circular CNOT Circuits: Definition, Analysis and Application to Fault-Tolerant Quantum CircuitsPublished by Springer Science and Business Media LLC ,2016
- Exact Reordering of Circuit Lines for Nearest Neighbor Quantum ArchitecturesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014
- Optimization in dynamic environments: a survey on problems, methods and measuresSoft Computing, 2010
- Synthesis of quantum circuits for linear nearest neighbor architecturesQuantum Information Processing, 2010
- Quantum Circuit PlacementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008
- An Efficient Transformation Of The Generalized Traveling Salesman ProblemINFOR: Information Systems and Operational Research, 1993