Journal: ACM Transactions on Quantum Computing

Abbreviation

Publisher

Association for Computing Machinery

Journal Volumes

ISSN

2643-6809
2643-6817

Description

Filters

20223
Reset filters

Search Results

Publications 1 - 3 of 3
  • Exact and Practical Pattern Matching for Quantum Circuit Optimization
    Item type: Journal Article
    Iten, Raban; Moyard, Romain; Metger, Tony; et al. (2022)
    ACM Transactions on Quantum Computing
    Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern, in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.
  • QIRO: A Static Single Assignment-based Quantum Program Representation for Optimization
    Item type: Journal Article
    Ittah, David; Häner, Thomas; Kliuchnikov, Vadym; et al. (2022)
    ACM Transactions on Quantum Computing
    We propose an IR for quantum computing that directly exposes quantum and classical data dependencies for the purpose of optimization. The Quantum Intermediate Representation for Optimization (QIRO) consists of two dialects, one input dialect and one that is specifically tailored to enable quantum-classical co-optimization. While the first employs a perhaps more intuitive memory-semantics (quantum operations act on qubits via side-effects), the latter uses value-semantics (operations consume and produce states) to integrate quantum dataflow in the IR's Static Single Assignment (SSA) graph. Crucially, this allows for a host of optimizations that leverage dataflow analysis. We discuss how to map existing quantum programming languages to the input dialect and how to lower the resulting IR to the optimization dialect. We present a prototype implementation based on MLIR that includes several quantum-specific optimization passes. Our benchmarks show that significant improvements in resource requirements are possible even through static optimization. In contrast to circuit optimization at run time, this is achieved while incurring only a small constant overhead in compilation time, making this a compelling approach for quantum program optimization at application scale.
  • Enhancing the Quantum Linear Systems Algorithm Using Richardson Extrapolation
    Item type: Journal Article
    Carrera Vazquez, Almudena; Hiptmair, Ralf; Woerner, Stefan (2022)
    ACM Transactions on Quantum Computing
    We present a quantum algorithm to solve systems of linear equations of the form Ax=b, where A is a tridiagonal Toeplitz matrix and b results from discretizing an analytic function, with a circuit complexity of O(1/√ε, poly (log κ, log N)), where N denotes the number of equations, ε is the accuracy, and κ the condition number. The repeat-until-success algorithm has to be run O(κ/(1-ε)) times to succeed, leveraging amplitude amplification, and needs to be sampled O(1/ε2) times. Thus, the algorithm achieves an exponential improvement with respect to N over classical methods. In particular, we present efficient oracles for state preparation, Hamiltonian simulation, and a set of observables together with the corresponding error and complexity analyses. As the main result of this work, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation (QPE) within the algorithm with 1/√ε circuits that can be run in parallel each with circuit complexity 1/√ ε instead of 1/ε. Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach is not limited to the considered setting and can be applied to more general problems where Hamiltonian simulation is approximated via product formulae, although our theoretical results would need to be extended accordingly. All the procedures presented are implemented with Qiskit and tested for small systems using classical simulation as well as using real quantum devices available through the IBM Quantum Experience.
Publications 1 - 3 of 3