Software Pipelining for Quantum Loop Programs

• URL: http://arxiv.org/abs/2012.12700v1
• Date: Wed, 23 Dec 2020 14:27:05 GMT
• Title: Software Pipelining for Quantum Loop Programs
• Authors: Jingzhe Guo, Mingsheng Ying
• Abstract summary: We present a software pipelining exploiting instruction-level parallelism in quantum loop programs. The method is then evaluated on some test cases, including popular applications like QAOA, and compared with several baseline results. This is the first step towards optimization of a quantum program with such loop control flow as far as we know.
• Score: 1.1878820609988696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a method for performing software pipelining on quantum for-loop programs, exploiting parallelism in and across iterations. We redefine concepts that are useful in program optimization, including array aliasing, instruction dependency and resource conflict, this time in optimization of quantum programs. Using the redefined concepts, we present a software pipelining algorithm exploiting instruction-level parallelism in quantum loop programs. The optimization method is then evaluated on some test cases, including popular applications like QAOA, and compared with several baseline results. The evaluation results show that our approach outperforms loop optimizers exploiting only in-loop optimization chances by reducing total depth of the loop program to close to the optimal program depth obtained by full loop unrolling, while generating much smaller code in size. This is the first step towards optimization of a quantum program with such loop control flow as far as we know.

Related papers

• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation [10.655710695515044]
  Numerous quantum algorithms require the use of quantum error correction to overcome the unreliability of physical qubits. error correction imposes a performance bottleneck, known as T-complexity, that can make implementation of an algorithm run more slowly than on idealized hardware. We present a cost model that a developer can use to analyze the T-complexity of a program and pinpoint the sources of slowdown.
  arXiv  Detail & Related papers  (2023-11-21T18:32:05Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices [7.99536002595393]
  We show how to leverage quantum speed-up of an eigensolver in speeding up an SDP solver utilizing the cutting-plane method. We show that the RCP method is very robust to noise in the boundary oracle, which may make RCP suitable for use even on noisy quantum devices.
  arXiv  Detail & Related papers  (2021-10-07T12:42:23Z)
• Progress towards analytically optimal angles in quantum approximate optimisation [0.0]
  The Quantum Approximate optimisation algorithm is a $p$ layer, time-variable split operator method executed on a quantum processor. We prove that optimal parameters for $p=1$ layer reduce to one free variable and in the thermodynamic limit, we recover optimal angles. We moreover demonstrate that conditions for vanishing gradients of the overlap function share a similar form which leads to a linear relation between circuit parameters, independent on the number of qubits.
  arXiv  Detail & Related papers  (2021-09-23T18:00:13Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Enabling Dataflow Optimization for Quantum Programs [11.71212583708166]
  IR for quantum computing exposes quantum and classical data dependencies for the purpose of optimization. We present a prototype implementation based on MLIR that includes several quantum-specific optimization passes.
  arXiv  Detail & Related papers  (2021-01-26T19:01:12Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Warm-starting quantum optimization [6.832341432995627]
  We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem. This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
  arXiv  Detail & Related papers  (2020-09-21T18:00:09Z)

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.