Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits

Overview

• Quantum circuits need to be mapped to specific quantum processors for execution.
• This process is called layout synthesis and requires SWAP gate insertions to schedule 2-qubit gates on connected physical qubits.
• With the growing number of qubits in NISQ processors, scalable layout synthesis methods are crucial.
• Existing heuristic approaches have large optimality gaps, so scalable exact methods are needed.
• Recent exact and near-optimal approaches can handle moderate circuits, but large deep circuits are still challenging.

Plain English Explanation

Quantum computers use specialized hardware called quantum processors to run quantum circuits - sequences of quantum operations. Before a quantum circuit can be executed, it needs to be mapped or laid out onto the specific hardware of a quantum processor. This process is called layout synthesis.

A key challenge in layout synthesis is that 2-qubit gates in the quantum circuit can only be executed on pairs of physically connected qubits in the processor. To handle this, SWAP gates need to be inserted into the circuit to rearrange the qubits and make the necessary connections.

As quantum processors continue to grow in the number of qubits, scalable layout synthesis methods become increasingly important. However, existing heuristic (rule-of-thumb) approaches often have large gaps between the quality of their solutions and the optimal solution. This means there is significant room for improvement.

To address this, researchers are exploring exact optimization methods that can find the truly optimal layout. While recent exact and near-optimal approaches have made progress, they still struggle to handle very large and complex quantum circuits. A new, more scalable solution is needed.

Technical Explanation

This work proposes a SAT encoding (a way to represent the problem as a Boolean satisfiability problem) for layout synthesis. The key idea is to plan the circuit execution in parallel, applying 1 SWAP and a group of CNOTs (a common 2-qubit gate) at each time step.

By incorporating domain-specific information, the researchers are able to maintain optimality in these parallel plans while scaling to large and deep quantum circuits. Their results show this approach significantly outperforms leading exact and near-optimal methods, achieving up to 100x speedups.

For the first time, the researchers can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit quantum processor platforms, using up to 17 SWAP gates. Importantly, in addition to finding the optimal number of SWAPs, their approach also produces near-optimal depth (a measure of circuit execution time) for the mapped circuits.

Critical Analysis

The paper demonstrates impressive scalability improvements over prior state-of-the-art methods for optimal quantum circuit layout synthesis. By introducing a novel parallel planning approach with SAT encoding, the researchers are able to handle significantly larger and deeper circuits than previous exact techniques.

However, the paper does not discuss the potential limitations of this approach. For example, it is unclear how the method would scale to even larger quantum processors with hundreds or thousands of qubits, or how it would perform on circuits with different structures and gate counts. Additionally, the paper does not explore the tradeoffs between optimality, execution depth, and runtime of the synthesis process.

Further research could investigate the robustness of this SAT-based parallel planning approach, compare it to other emerging layout synthesis techniques (e.g. those using machine learning), and examine its performance on a wider range of benchmark circuits and hardware configurations. Exploring these aspects would help provide a more comprehensive understanding of the strengths, weaknesses, and applicability of this new layout synthesis method.

Conclusion

This work presents a significant advance in scalable, optimal quantum circuit layout synthesis. By encoding the problem as a SAT instance and leveraging parallel planning, the researchers demonstrate the ability to map large, deep quantum circuits to realistic hardware platforms in an optimal manner.

These improvements in layout synthesis are a crucial step towards realizing the full potential of noisy intermediate-scale quantum (NISQ) computers, where the efficient use of limited qubit connectivity and hardware resources is paramount. As quantum hardware continues to scale, this research paves the way for more practical, high-performance quantum computing.