Programming for quantum computers is complicated and time-consuming, because quantum operations are counterintuitive and their combined effects are difficult to understand. Existing tools allow automatic synthesis of quantum programs, which releases the burden of handwriting. However, many existing systems arrange predetermined operators in successive manner to gradually reduce the gap with requirements; these methods are quick but often produce lengthy programs, and they are difficult to adopt for new operators. Other systems depend on stochastic or heuristic search; they identify near-optimal programs for certain cases, but it is not easy to tune the algorithms for a wide range of cases. We propose a system that produces compact programs for most cases and easily evolves with new operators. The system automatically learns the roles of available operators by composing various possible programs. Based on the knowledge, it selects a subset of operators most appropriate for requirements and uses them to compose a program. The learning is geared toward concise programs; thus, the system tends to produce programs with the fewest operators possible. We implemented the system and evaluated it by synthesizing over 400 programs. In comparison with a state-of-the-art system, the proposed system produced programs with approximately 40-times fewer operators at the cost of increased synthesis time from seconds to minutes. We also observed that the system successfully adopted new operators by learning their differences from existing operators and utilizing them in right places. We believe that the system provides a basis of utilizing machine learning for quantum program synthesis.
Programming for quantum computers is complicated and time-consuming, because quantum operations are counterintuitive and their combined effects are difficult to understand. Existing tools allow automatic synthesis of quantum programs, which releases the burden of handwriting. However, many existing systems arrange predetermined operators in successive manner to gradually reduce the gap with requirements; these methods are quick but often produce lengthy programs, and they are difficult to adopt for new operators. Other systems depend on stochastic or heuristic search; they identify near-optimal programs for certain cases, but it is not easy to tune the algorithms for a wide range of cases. We propose a system that produces compact programs for most cases and easily evolves with new operators. The system automatically learns the roles of available operators by composing various possible programs. Based on the knowledge, it selects a subset of operators most appropriate for requirements and uses them to compose a program. The learning is geared toward concise programs; thus, the system tends to produce programs with the fewest operators possible. We implemented the system and evaluated it by synthesizing over 400 programs. In comparison with a state-of-the-art system, the proposed system produced programs with approximately 40-times fewer operators at the cost of increased synthesis time from seconds to minutes. We also observed that the system successfully adopted new operators by learning their differences from existing operators and utilizing them in right places. We believe that the system provides a basis of utilizing machine learning for quantum program synthesis.
Recent years have witnessed the fast development of quantum computing. Researchers around the world are eager to run larger and larger quantum algorithms that promise speedups impossible to any classical algorithm. However, the available quantum computers are still volatile and error-prone. Thus, layout synthesis, which transforms quantum programs to meet these hardware limitations, is a crucial step in the realization of quantum computing. In this paper, we present two synthesizers, one optimal and one approximate but nearly optimal. Although a few optimal approaches to this problem have been published, our optimal synthesizer explores a larger solution space, thus is optimal in a stronger sense. In addition, it reduces time and space complexity exponentially compared to some leading optimal approaches. The key to this success is a more efficient spacetime-based variable encoding of the layout synthesis problem as a mathematical programming problem. By slightly changing our formulation, we arrive at an approximate synthesizer that is even more efficient and outperforms some leading heuristic approaches, in terms of additional gate cost, by up to 100%, and also fidelity by up to 10x on a comprehensive set of benchmark programs and architectures. For a specific family of quantum programs named QAOA, which is deemed to be a promising application for near-term quantum computers, we further adjust the approximate synthesizer by taking commutation into consideration, achieving up to 75% reduction in depth and up to 65% reduction in additional cost compared to the tool used in a leading QAOA study.
Quantum programs are notoriously difficult to code and verify due to unintuitive quantum knowledge associated with quantum programming. Automated tools relieving the tedium and errors associated with low-level quantum details would hence be highly desirable. In this paper, we initiate the study of program synthesis for quantum unitary programs that recursively define a family of unitary circuits for different input sizes, which are widely used in existing quantum programming languages. Specifically, we present QSynth, the first quantum program synthesis framework, including a new inductive quantum programming language, its specification, a sound logic for reasoning, and an encoding of the reasoning procedure into SMT instances. By leveraging existing SMT solvers, QSynth successfully synthesizes 10 quantum unitary programs including quantum arithmetic programs, quantum eigenvalue inversion, quantum teleportation and Quantum Fourier Transformation, which can be readily transpiled to executable programs on major quantum platforms, e.g., Q#, IBM Qiskit, and AWS Braket.
In recent years, there has been a proliferation of quantum algorithms, primarily due to their exponential speedup over their classical counterparts. Quantum algorithms find applications in various domains, including machine learning, molecular simulation, and cryptography. However, extensive knowledge of linear algebra and quantum mechanics are required to program a quantum computer, which might not be feasible for traditional software programmers. Moreover, current quantum programming paradigm is difficult to scale and integrate quantum circuits to achieve complex functionality. To this end, in this paper, we introduce QHLS, a quantum high-level synthesis (HLS) framework. To the best of our knowledge, this is the first HLS framework for quantum circuits. The proposed QHLS allows quantum programmers to start with high-level behavioral descriptions (e.g., C, C++) and automatically generate the corresponding quantum circuit; thus, reducing the complexity of programming a quantum computer. Our experimental results demonstrate the success of QHLS in translating high-level behavioral software programs containing arithmetic, logical, and conditional statements.
Quantum unitary synthesis addresses the problem of translating abstract quantum algorithms into sequences of hardware-executable quantum gates. Solving this task exactly is infeasible in general due to the exponential growth of the underlying combinatorial search space. Existing approaches suffer from misaligned optimization objectives, substantial training costs and limited generalization across different qubit counts. We mitigate these limitations by using supervised learning to approximate the minimum description length of residual unitaries and combining this estimate with stochastic beam search to identify near optimal gate sequences. Our method relies on a lightweight model with zero-shot generalization, substantially reducing training overhead compared to prior baselines. Across multiple benchmarks, we achieve faster wall-clock synthesis times while exceeding state-of-the-art methods in terms of success rate for complex circuits.
Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.
Abstract Despite rapid progress in the field, it is still challenging to discover new ways to leverage quantum computation: all quantum algorithms must be designed by hand, and quantum mechanics is notoriously counterintuitive. In this paper, we study how artificial intelligence, in the form of program synthesis, may help overcome some of these difficulties, by showing how a computer can incrementally learn concepts relevant to quantum circuit synthesis with experience, and reuse them in unseen tasks. In particular, we focus on the decomposition of unitary matrices into quantum circuits, and show how, starting from a set of elementary gates, we can automatically discover a library of useful new composite gates and use them to decompose increasingly complicated unitaries.