A monte carlo tree search framework for quantum circuit transformation
Authors:
Open Access
- 2 November 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-7
Abstract
In Noisy Intermediate-Scale Quantum (NISQ) era, quantum processing units (QPUs) suffer from, among others, highly limited connectivity between physical qubits. To make a quantum circuit executable, a circuit transformation process is necessary to transform it into a functionally equivalent one so that the connectivity constraints imposed by the QPU are satisfied. Due to the high branching factor and vast search space, almost all existing algorithms search very shallowly and thus, very often, can reach (at most) locally optimal solutions. We propose a Monte Carlo Tree Search framework to tackle this problem, which enables the search process to go deeper. In particular, we design, by taking both short- and long-term rewards into consideration, a scoring mechanism, and propose to use a fast random strategy for simulation. The thus designed search algorithm is polynomial in all relevant parameters and empirical results on extensive realistic circuits show that it can reduce, in average, the size of the output circuits by at least 30% when compared with the state-of-the-art algorithms on IBM Q20.Keywords
All Related Versions
Funding Information
- The National Key R&D Program of China (2018YFA0306704)
- The Australian Research Council (DP180100691)
This publication has 19 references indexed in Scilit:
- Compiling quantum circuits to realistic hardware architectures using temporal plannersQuantum Science and Technology, 2018
- Mastering the game of Go without human knowledgeNature, 2017
- Temporal Planning for Compilation of Quantum Approximate Optimization Circuits2017
- Mastering the game of Go with deep neural networks and tree searchNature, 2016
- Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits2015
- A Survey of Monte Carlo Tree Search MethodsIEEE Transactions on Computational Intelligence and AI in Games, 2012
- Synthesis of quantum circuits for linear nearest neighbor architecturesQuantum Information Processing, 2010
- Synthesis of quantum-logic circuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- Bandit Based Monte-Carlo Planning2006
- Elementary gates for quantum computationPhysical Review A, 1995