Search

In the Noisy Intermediate Scale Quantum (NISQ) era, finding implementations of quantum algorithms that minimize the number of expensive and error prone multi-qubit gates is vital to ensure computations produce meaningful outputs. Unitary synthesis, the process of finding a quantum circuit that implements some target unitary matrix, is able to solve this problem optimally in many cases. However, current bottom-up unitary synthesis algorithms are limited by their exponentially growing run times. We show how applying machine learning to unitary datasets permits drastic speedups for synthesis algorithms. This paper presents QSeed, a seeded synthesis algorithm that employs a learned model to quickly propose resource efficient circuit implementations of unitaries. QSeed maintains low gate counts and offers a speedup of $3.7\times$ in synthesis time over the state of the art for a 64 qubit modular exponentiation circuit, a core component in Shor's factoring algorithm. QSeed's performance improvements also generalize to families of circuits not seen during the training process., 11 pages, 10 figures

We propose a novel hierarchical qubit mapping and routing algorithm. First, a circuit is decomposed into blocks that span an identical number of qubits. In the second stage permutation-aware synthesis (PAS), each block is optimized and synthesized in isolation. In the third stage a permutation-aware mapping (PAM) algorithm maps the blocks to the target device based on the information from the second stage. Our approach is based on the following insights: (1) partitioning the circuit into blocks is beneficial for qubit mapping and routing; (2) with PAS, any block can implement an arbitrary input-output qubit mapping that reduces the gate count; and (3) with PAM, for two adjacent blocks we can select input-output permutations that optimize each block together with the amount of communication required at the block boundary. Whereas existing mapping algorithms preserve the original circuit structure and only introduce "minimal" communication via inserting SWAP or bridge gates, the PAS+PAM approach can additionally change the circuit structure and take full advantage of hardware-connectivity. Our experiments show that we can produce better-quality circuits than existing mapping algorithms or commercial compilers (Qiskit, TKET, BQSKit) with maximum optimization settings. For a combination of benchmarks we produce circuits shorter by up to 68% (18% on average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than TKET, and up to 67% (21% on average) fewer gates than BQSKit. Furthermore, the approach scales, and it can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure., 12 pages, 9 figures, 5 tables

Unitary synthesis is an optimization technique that can achieve optimal multi-qubit gate counts while mapping quantum circuits to restrictive qubit topologies. Because synthesis algorithms are limited in scalability by their exponentially growing run time and memory requirements, application to circuits wider than 5 qubits requires divide-and-conquer partitioning of circuits into smaller components. In this work, we will explore methods to reduce the depth (program run time) and multi-qubit gate instruction count of wide (16-100 qubit) mapped quantum circuits optimized with synthesis. Reducing circuit depth and gate count directly impacts program performance and the likelihood of successful execution for quantum circuits on parallel quantum machines. We present TopAS, a topology aware synthesis tool built with the \emph{BQSKit} framework that preconditions quantum circuits before mapping. Partitioned subcircuits are optimized and fitted to sparse qubit subtopologies in a way that balances the often opposing demands of synthesis and mapping algorithms. This technique can be used to reduce the depth and gate count of wide quantum circuits mapped to the sparse qubit topologies of Google and IBM. Compared to large scale synthesis algorithms which focus on optimizing quantum circuits after mapping, TopAS is able to reduce depth by an average of 35.2% and CNOT gate count an average of 11.5% when targeting a 2D mesh topology. When compared with traditional quantum compilers using peephole optimization and mapping algorithms from the Qiskit or $t|ket\rangle$ toolkits, our approach is able to provide significant improvements in performance, reducing CNOT counts by 30.3% and depth by 38.2% on average., Comment: 12 pages, 11 figures