Quantum Circuit Layout Optimized for 100+ Qubits

The article discusses the challenges and solutions in layout synthesis for quantum circuits, a key aspect of quantum computing. The process involves mapping a quantum circuit to a quantum processor, requiring the insertion of SWAP gates. The authors propose a SAT encoding based on parallel plans for optimal layout synthesis, which scales to large and deep circuits while maintaining optimality. The study’s results show that their tool outperforms leading near-optimal tools and highlights the limitations of heuristic approaches. This research contributes significantly to the development of practical quantum computing.

What is Layout Synthesis for Quantum Circuits?

Quantum computing is a rapidly evolving field that promises to revolutionize the way we process information. One of the key challenges in this field is the layout synthesis for quantum circuits. This involves mapping a quantum circuit to a quantum processor. The process requires the insertion of SWAP gates to schedule 2-qubit gates only on connected physical qubits. As the number of qubits in Noisy Intermediate-Scale Quantum (NISQ) processors increases, scalable layout synthesis becomes increasingly important.

The Quantum Layout Mapping problem takes a quantum circuit and a coupling map (which shows the connectedness between physical qubits) as input. The output is an equivalent quantum circuit mapped to the physical qubits such that any binary operation only happens on connected qubits. This process involves the insertion of SWAP gates. However, noise is inherent to qubits in NISQ processors, and additional SWAP gates increase both the 2-qubit gate count and the circuit depth. Therefore, minimizing error is of utmost importance for any practical quantum computing.

How is Optimal Layout Synthesis Achieved?

Optimal Layout Synthesis has been studied before. Several heuristic approaches exist which optimize various metrics. The classical algorithm for heuristic mapping is SABRE in Qiskit. Other approaches used include A* with cost metrics, MAXSAT, temporal planning, and constraint programming, all aimed at minimizing circuit depth.

While heuristic approaches are fast and scalable, their suboptimal mappings may result in high error rates. Optimizing fidelity with exact approaches can result in circuits with the lowest error rate. However, optimizing fidelity is extremely hard and does not scale beyond small circuits. Circuit depth and 2-qubit gate count optimization are better alternatives for scalability.

What is the Contribution of this Study?

In this study, the authors propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, they maintain optimality in parallel plans while scaling to large and deep circuits. They also propose two-way constraints for CNOT dependencies for better dependency propagation. In addition, they provide variations of their encoding with bridges and relaxed dependencies via commutation. In all variations, they only add provably optimal number of bridges/SWAPs.

For experimental evaluation, they consider two benchmark sets: Standard benchmarks from previous papers and Deep VQE benchmarks. For comparison, they consider leading near-optimal tool TBOLSQ2 and heuristic SABRE. For mapping, they consider 4 NISQ processors: Melbourne (14 qubits), Sycamore (54 qubits), Rigetti (80 qubits), and Eagle (127 qubits).

What are the Results of the Study?

The results of the study show that their encoding can optimally map deep circuits onto large platforms with up to 127 qubits. Their tool outperforms the leading near-optimal tool TBOLSQ2 up to 100x while always adding the optimal number of SWAPs. They show that while adding optimal SWAPs, they also report near-optimal depth in the mapped circuits. They also confirm that heuristic approaches like SABRE add too many SWAPs.

What is the Significance of this Study?

The significance of this study lies in its contribution to the field of quantum computing. By proposing a SAT encoding based on parallel plans, the authors have provided a scalable solution for layout synthesis of quantum circuits. This is a significant step forward in the development of practical quantum computing. The results of the study also highlight the limitations of heuristic approaches, emphasizing the need for exact methods in layout synthesis. This study, therefore, provides valuable insights for researchers and practitioners in the field of quantum computing.