Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
- URL: http://arxiv.org/abs/2008.09331v4
- Date: Tue, 25 Jan 2022 06:23:06 GMT
- Title: Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
- Authors: Xiangzhen Zhou, Yuan Feng, Sanjiang Li
- Abstract summary: 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 effectively executable, a circuit transformation process is necessary to transform it.
We propose a Monte Carlo Tree Search (MCTS) framework to tackle the circuit transformation problem.
- Score: 6.72166630054365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 effectively executable, a circuit
transformation process is necessary to transform it, with overhead cost the
smaller the better, into a functionally equivalent one so that the connectivity
constraints imposed by the QPU are satisfied. While several algorithms have
been proposed for this goal, the overhead costs are often very high, which
degenerates the fidelity of the obtained circuits sharply. One major reason for
this lies in that, due to the high branching factor and vast search space,
almost all these algorithms only search very shallowly and thus, very often,
only (at most) locally optimal solutions can be reached. In this paper, we
propose a Monte Carlo Tree Search (MCTS) framework to tackle the circuit
transformation problem, which enables the search process to go much deeper. The
general framework supports implementations aiming to reduce either the size or
depth of the output circuit through introducing SWAP or remote CNOT gates. The
algorithms, called MCTS-Size and MCTS-Depth, are polynomial in all relevant
parameters. Empirical results on extensive realistic circuits and IBM Q Tokyo
show that the MCTS-based algorithms can reduce the size (depth, resp.) overhead
by, on average, 66% (84%, resp.) when compared with tket, an industrial level
compiler.
Related papers
- Quantum Multiplexer Simplification for State Preparation [0.7270112855088837]
We propose an algorithm that detects whether a given quantum state can be factored into substates.
The simplification is done by eliminating controls of quantum multiplexers.
Considering efficiency in terms of depth and number of CNOT gates, our method is competitive with the methods in the literature.
arXiv Detail & Related papers (2024-09-09T13:53:02Z) - Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
We develop a reinforcement learning-based quantum compiler for a superconducting processor.
We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths.
Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
arXiv Detail & Related papers (2024-06-18T01:49:48Z) - A Fast and Adaptable Algorithm for Optimal Multi-Qubit Pathfinding in Quantum Circuit Compilation [0.0]
This work focuses on multi-qubit pathfinding as a critical subroutine within the quantum circuit compilation mapping problem.
We introduce an algorithm, modelled using binary integer linear programming, that navigates qubits on quantum hardware optimally with respect to circuit SWAP-gate depth.
We have benchmarked the algorithm across a variety of quantum hardware layouts, assessing properties such as computational runtimes, solution SWAP depths, and accumulated SWAP-gate error rates.
arXiv Detail & Related papers (2024-05-29T05:59:15Z) - Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs.
We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
arXiv Detail & Related papers (2024-05-01T20:49:50Z) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
Variational quantum algorithms have become the de facto model for current quantum computations.
One such problem is unstructured search which consists on finding a particular bit of string.
We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
arXiv Detail & Related papers (2024-03-22T18:00:03Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs)
We propose a new protocol for approximating TN states using realistic quantum circuits.
Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
arXiv Detail & Related papers (2022-09-01T17:08:41Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem.
The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment.
We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
arXiv Detail & Related papers (2022-04-18T21:45:13Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.