Fewer Quantum Gates Mean Simpler, More Powerful Computers

Arianne Meijer-van de Griend and colleagues at University of Helsinki have found a new approach to qubit routing that sharply reduces computational cost. Synthesising an n-qubit phase polynomial requires between O(gn/max(log g, 1)) and O(gn) CNOT gates. By synthesising only allowed gates, routing overhead can be minimised to a factor of 1 to 4, effectively achieving qubit routing for almost no additional computational expense. The finding offers a pathway to optimise quantum algorithms on restricted hardware architectures without substantial performance penalties.

Phase polynomial synthesis enables hardware-aware quantum circuit construction

The advancement centres on a shift towards building quantum circuits using effectively pre-fabricated components. Phase polynomials, circuits of CNOT and RZ gates, function as building blocks, similar to different coloured LEGO bricks used to construct a larger model. Instead of assembling a complete circuit and then attempting to map it onto a quantum processor, the focus is on synthesising these phase polynomials directly to adhere to the hardware’s limitations. This approach is particularly relevant given the current state of quantum hardware, where qubit connectivity is often limited and not fully all-to-all, meaning not every qubit can directly interact with every other qubit. The limitations of physical qubit connectivity necessitate the use of SWAP gates to move quantum information around the chip, adding significant overhead to computations.

This means selecting only ‘allowed’ CNOT gates, fundamental operations manipulating qubits, akin to logic gates in a conventional computer, that correspond to the processor’s native connections. A novel approach to quantum circuit design prioritises adherence to a quantum processor’s physical limitations from the outset. Mathematical proofs demonstrate that synthesising these phase polynomials requires between O(gn/max(log g, 1)) and O(gn) CNOT gates, where ‘n’ represents the number of qubits and ‘g’ the number of terms. The parameter ‘g’ signifies the complexity of the phase polynomial, representing the number of individual phase operations required. A key benefit of this technique is avoiding qubit routing, which typically adds O (log n) to O(n log² n) CNOT gates. Consequently, qubit routing now has nearly constant overhead, a significant improvement over previously adapting circuits post-synthesis which incurred substantial computational penalties. The reduction in gate count directly translates to shorter circuit execution times and reduced error rates, crucial for achieving meaningful quantum computation.

Hardware-aware circuit synthesis enables near constant qubit routing overhead

Routing overhead has been reduced to a factor of 1 to 4, a substantial improvement over previous methods requiring O (log n) to O(n log² n) CNOT gates. This breakthrough circumvents the need for SWAP-based routing, a technique utilising CNOT gates to exchange qubit states, by synthesising circuits directly compatible with a quantum processor’s architecture. SWAP gates, while necessary for general quantum computation on limited hardware, introduce additional errors and increase circuit depth. A single CNOT gate can toggle qubit participation in multiple interactions, streamlining the process and reducing computational load. This is achieved by carefully selecting the order and arrangement of CNOT gates within the phase polynomial synthesis, minimising the need for qubit rearrangements.

Phase polynomials, circuits composed of CNOT and RZ gates, alongside Hadamard gates, form a universal gate set enabling efficient qubit routing. A mathematical proof establishes that synthesizing a phase polynomial with g terms acting on n qubits requires at least O( gn/max(log g, 1)) and at most O(gn) CNOT gates. The minimum and maximum CNOT complexity remains consistent with unconstrained synthesis, offering comparable performance. This means that the method does not inherently sacrifice the potential for optimal circuit construction, but rather provides a means to achieve it within hardware constraints. This results in a routing overhead factor of 1 ≤ α ≤ 4 when synthesizing allowed gates, indicating minimal additional CNOTs are needed for efficient operation. The value of α being close to 1 represents an ideal scenario where the hardware constraints have minimal impact on the circuit’s complexity.

Efficient quantum circuit construction using phase polynomials and Hadamard gates

Designing quantum circuits to fit a processor’s limitations from the start promises substantial gains in efficiency, sidestepping the costly process of rearranging qubits after initial optimisation. This work concentrates on building circuits from phase polynomials and Hadamard gates, powerful tools, but does not represent a complete picture of all possible quantum algorithms. While these components form a universal set, meaning any quantum computation can theoretically be constructed from them, it remains unclear how easily this synthesis method scales to more complex programs utilising a wider range of quantum gates. The universality stems from the ability to decompose any quantum operation into a sequence of CNOT, RZ, and Hadamard gates, although the resulting circuit may not always be optimal in terms of gate count or depth.

Acknowledging that scaling to arbitrarily complex programs remains an open challenge does not diminish the immediate value of this approach. Focusing on phase polynomials, calculations using quantum phases, and Hadamard gates, which manipulate quantum states, offers a pragmatic route to more efficient circuit design for near-term quantum computers. By pre-planning for hardware constraints, the need for later qubit rearrangement, a costly and time-consuming process, can be sharply reduced, improving overall performance. This is particularly important for noisy intermediate-scale quantum (NISQ) devices, where qubit coherence times are limited and errors accumulate rapidly.

This work establishes a new model for quantum circuit construction, moving beyond post-optimisation qubit routing to a method prioritising hardware limitations from the circuit’s inception. Utilising building blocks like sequences of controlled-NOT and rotation gates, and Hadamard gates, allows for synthesising quantum circuits directly to match a processor’s connectivity. Achieving routing with a minimal overhead factor of between one and four demonstrates a substantial improvement over previous techniques demanding considerably more computational resources, paving the way for more efficient quantum computation. Future research will likely focus on extending this approach to encompass a broader range of quantum gates and algorithms, ultimately aiming to unlock the full potential of quantum computing on realistic hardware platforms.

The research demonstrates a method for constructing quantum circuits with a guaranteed number of CNOT gates, ranging from at least O(gn/max(log g, 1)) to at most O(gn), where ‘g’ represents the number of terms and ‘n’ the number of qubits. This matters because it provides a more efficient way to design circuits for near-term quantum computers by considering hardware limitations during the initial stages of construction. The authors achieved qubit routing with a minimal overhead factor of between one and four, representing an improvement over previous methods. Future work intends to expand this approach to include a wider variety of quantum gates and algorithms.