Flexible constraint compilation in the parity architecture
03/05/2023
In the past few years, quantum computers have experienced impressive advancements in terms of number of qubits as well as coherence, but one of the major challenges in building scalable quantum computers remains qubit connectivity. Quantum noise, for example crosstalk errors, can lead to issues like frequency crowding, limiting the number of qubits that are connected.
When the ParityQC Architecture was first introduced in 2015, it was clear that it could be a straightforward solution for the issue of qubit connectivity, offering a way to solve optimization problems with quantum computers. And its field of application proved not to be limited to optimization problems alone. A recently published piece of research showed that the architecture can be efficiently used to implement arbitrary quantum algorithms, through a universal gate set.
But one important issue still remained a challenge until now: the compilation of hard optimization problems to the ParityQC Architecture on restricted quantum hardware (for example, devices with less than square-lattice nearest-neighbor connectivity). These optimization problems can include constraints and higher-order interactions, which are notoriously difficult to implement.
This is the issue that is tackled in the paper “Flexible Constraint Compilation in the Parity Architecture” by Roeland ter Hoeven, Anette Messinger, and Wolfgang Lechner, out now on arXiv as a pre-print. In this paper, the authors present a way to perform the parity compilation on arbitrary devices for arbitrary problems, paving the way to the compilation of hard optimization problems on any type of quantum computing platform. Previous approaches required all parity constraints to be local, which made it impossible to complete the parity mapping for some sparsely connected devices (e.g. linear chains or hexagonal lattices). This novel solution is based a new technique called bridging, that allows to implement non-local constraints in a more efficient way than by using SWAP gates.
The more “non-local” the constraints are, the more resources (e.g. CNOT gates) they require. Therefore, a few methods are proposed, which allow to minimize the non-locality of the constraints for a given optimization problem and hardware layout. The researchers also show that for every optimization problem mapped to the ParityQC Architecture, one can find an implementation of the constraint terms using nearest-neighbor CNOT (or other entangling) gates and local rotations. The authors then provide some tools to make an optimal choice of constraints and qubit layout, in order to minimize the CNOT count or circuit depth.
The main steps towards this are:
1. Finding a valid set of constraints for a given parity mapping, where the maximum number of qubits in each constraint is restricted.
2. Implementing (potentially non-local) constraints using local operations.
3. Evaluating and minimizing the cost of implementing a constraint or a set of constraints based on the position of the corresponding qubits and the connectivity of the physical device.
The presented approach can be used both to improve the circuit implementation on a given device, and to design future devices in a way that keeps the circuit depth manageable for relevant problems. The authors demonstrate the power of the bridge technique to implement parity constraints, but its application actually goes beyond the ParityQC Architecture: it can also improve the implementation of many other non-local operators.
Read the pre-print on arXiv.