Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits

• URL: http://arxiv.org/abs/2201.06508v1
• Date: Mon, 17 Jan 2022 16:31:42 GMT
• Title: Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• Authors: Timoth\'ee Goubault de Brugi\`ere, Marc Baboulin, Beno\^it Valiron, Simon Martiel and Cyril Allouche
• Abstract summary: reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. We propose a new algorithm for any linear reversible operator by using an optimized version of the Gaussian elimination algorithm and a tuned LU factorization. Overall, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. These circuits can be efficiently simulated by classical computers and their size is polynomially bounded by the number of qubits, making them a good candidate to deploy efficient methods to reduce computational costs. We propose a new algorithm for synthesizing any linear reversible operator by using an optimized version of the Gaussian elimination algorithm coupled with a tuned LU factorization. We also improve the scalability of purely greedy methods. Overall, on random operators, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes: the custom Gaussian elimination algorithm provides the best results for large problem sizes (n > 150) while the purely greedy methods provide quasi optimal results when n < 30. On a benchmark of reversible functions, we manage to significantly reduce the CNOT count and the depth of the circuit while keeping other metrics of importance (T-count, T-depth) as low as possible.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• High Precision Fault-Tolerant Quantum Circuit Synthesis by Diagonalization using Reinforcement Learning [0.8341988468339112]
  Empirical search-based synthesis methods can generate good implementations for a more extensive set of unitaries. We leverage search-based methods to reduce the general unitary synthesis problem to one of diagonal unitaries. On a subset of algorithms of interest for future term applications, diagonalization can reduce T gate counts by up to 16.8%.
  arXiv  Detail & Related papers  (2024-08-31T12:10:32Z)
• SAGA: Synthesis Augmentation with Genetic Algorithms for In-Memory Sequence Optimization [0.0]
  MAGIC, or Memristor Aided Logic, is an approach which uses memory circuits which physically perform computation through write operations to memory. We detail the formation and implementation of these genetic algorithms and evaluate them over a number of open circuit implementations. Over the 10 benchmark circuits evaluated, these modifications lead to an overall improvement in the efficiency of in-memory circuit evaluation of 128% in the best case and 27.5% on average.
  arXiv  Detail & Related papers  (2024-06-14T03:00:42Z)
• Powerful Quantum Circuit Resizing with Resource Efficient Synthesis [0.4980726355048842]
  This paper introduces two such algorithms. The first one leverages gate-dependency rules to reduce qubit count by 61.6% or 45.3% when optimizing depth as well. The second algorithm finds resizing opportunities in previously unresizable circuits via dependency rules and other state-of-the-art tools.
  arXiv  Detail & Related papers  (2023-11-22T02:18:34Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• 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)
• Qubit-efficient entanglement spectroscopy using qubit resets [0.0]
  We develop qubit-efficient quantum algorithms for entanglement spectroscopy on NISQ devices. Our algorithms use fewer qubits than any previous efficient algorithm while achieving similar performance in the presence of noise. We also introduce the notion of effective circuit depth as a generalization of standard circuit depth suitable for circuits with qubit resets.
  arXiv  Detail & Related papers  (2020-10-06T23:22:57Z)

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.