NISQ circuit compilation is the travelling salesman problem on a torus

Understand

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.