Quantum Circuit Transformation: A Monte Carlo Tree Search Framework

Xiangzhen Zhou, Yuan Feng, Sanjiang LiACM Trans. Design Autom. Electr. Syst 2022 · DOI

TL;DR

This paper introduces a novel Monte Carlo Tree Search (MCTS) framework for transforming quantum circuits into a form executable on noisy, limited-connectivity quantum hardware. Their MCTS-based algorithms, MCTS-Size and MCTS-Depth, significantly reduce the overhead (in terms of gate count and circuit depth) compared to existing state-of-the-art compilers, demonstrating impressive performance gains.

What Problem Does This Paper Address?

Quantum computers, especially those in the Noisy Intermediate-Scale Quantum (NISQ) era, are plagued by limitations such as restricted qubit connectivity and high error rates. To run quantum algorithms on these devices, logical quantum circuits must be compiled into physical circuits that respect the hardware's architecture. This compilation process, known as Quantum Circuit Transformation (QCT), involves mapping logical qubits to physical ones and routing gates. Existing QCT algorithms often struggle with scalability and can lead to significant overheads in terms of added gates (like SWAPs) and circuit depth, which degrades the fidelity of the computation. The core challenge is to find an efficient transformation that minimizes these overheads while ensuring the circuit remains functionally equivalent.

Methods

The paper proposes a Monte Carlo Tree Search (MCTS) framework, inspired by its success in game playing, to tackle the QCT problem. The framework consists of five main modules: Selection, Expansion, Simulation, Backpropagation, and Decision.

  • Selection: Uses a UCT-like formula to balance exploration and exploitation of the search tree.
  • Expansion: Generates child nodes by applying relevant SWAP operations to enable more gates from the logical circuit to be executable.
  • Simulation: Employs a fast, random simulation strategy to estimate the long-term value of a state, focusing on a subset of the logical circuit for efficiency.
  • Backpropagation: Updates the values of ancestor nodes based on the simulation results and a discount factor.
  • Decision: Selects the best move (child node) to proceed with.

Two specific algorithms are derived from this framework:

  • MCTS-Size: Optimizes for minimizing the number of added SWAP gates (and thus CNOTs).
  • MCTS-Depth: Optimizes for minimizing the circuit depth, incorporating modifications to the reward and value functions to account for depth overhead.

The framework also allows for the incorporation of "remote CNOT" operations, which can execute CNOT gates between non-neighboring qubits without changing the qubit mapping, offering an alternative to SWAP gates.

Datasets

  • B114: A benchmark set of 114 circuits from Zulehner et al. (2018), comprising 554,497 gates (248,553 CNOTs) and 303,469 depths.
  • Breal: A set of 173 quantum circuits extracted from the Qiskit algorithm library, totaling 603,654 gates (260,589 CNOTs) and 413,734 depths.
  • B11: A smaller subset of 11 typical circuits from B114, used for parameter tuning.
  • Hypothetical AGs: Including Grid 4x5, Grid 4x4, 5x5, 6x6, 7x7, and 8x8, used for evaluating scalability and the impact of topology.
  • IBM Q20, IBM Rochester, and Google Sycamore: Real quantum processor architectures used for experimental evaluation.

Key Insights and Ideas

  • MCTS for QCT: Applying MCTS, a technique successful in complex decision-making domains like Go, proves effective for the combinatorial search problem of quantum circuit transformation.
  • Deep Search Capability: The MCTS framework allows for significantly deeper exploration of the search space compared to many existing heuristic algorithms, leading to better optimization.
  • Flexibility of MCTS: The framework is highly adaptable, allowing for easy modification of the objective function (e.g., minimizing size vs. depth) and the incorporation of new operations like remote CNOTs.
  • Trade-offs in QCT: The paper highlights that different QCT strategies (SWAP-based vs. remote CNOT) have varying impacts depending on the architecture and circuit, suggesting that a flexible approach is beneficial.
  • Importance of Depth: For NISQ devices, circuit depth is a critical metric, and MCTS-Depth demonstrates significant improvements in this area.

Key Results

  • MCTS-Size: Achieved an average improvement of 36.68% in gate overhead compared to SAHS and 59.24% compared to t|ket) on the B114 benchmark set.
  • MCTS-Depth: Reduced depth overhead by up to 84% compared to t|ket) on IBM Q20.
  • Scalability: The algorithm's running time scales polynomially with relevant parameters, and empirical tests show it is practically scalable.
  • Deeper Search: MCTS-Size consistently achieves a deeper search depth than SAHS, leading to better results.
  • Remote CNOT Impact: The effectiveness of remote CNOTs is architecture-dependent; they show significant improvements on grid-like architectures but less so on more connected ones like IBM Q20.

Limitations and Future Work

  • Parameter Tuning: The performance of MCTS algorithms is sensitive to parameter settings, and while empirical tuning was performed, further study on parameter correlation and optimization is suggested.
  • Initial Mappings: The performance can be influenced by the initial qubit mapping. While the paper uses standard initial mappings for comparison, exploring optimal initial mappings could yield further improvements.
  • Other Optimization Objectives: The authors suggest incorporating other objectives like fidelity and error rate into the evaluation criteria.
  • Parallelization: Developing a parallelized implementation of the MCTS framework is proposed as a future direction to achieve even better results more quickly.
  • Deterministic Simulation: For large architectures, a deterministic simulation strategy was found to outperform the random one, suggesting this could be a valuable enhancement.

Summary updated

BibTeX
@article{zhou2022quantum,
  author = {Xiangzhen Zhou and Yuan Feng and Sanjiang Li},
  title = {{Quantum Circuit Transformation: A Monte Carlo Tree Search Framework}},
  journal = {ACM Trans. Design Autom. Electr. Syst},
  year = {2022},
  doi = {10.1145/3514239},
}
Figure