Optimization of Quantum Systems Emulation via a Variant of the Bandwidth Minimization Problem

• URL: http://arxiv.org/abs/2404.15165v1
• Date: Tue, 23 Apr 2024 16:04:37 GMT
• Title: Optimization of Quantum Systems Emulation via a Variant of the Bandwidth Minimization Problem
• Authors: M. Yassine Naghmouchi, Joseph Vovrosh, Wesley da Silva Coelho, Alexandre Dauphin,
• Abstract summary: weighted-BMP is a variant of the Bandwidth Minimization Problem (BMP) We formulate the problem using a Mixed Linear Program (MILP) and solve it to optimality with a state of the art solver. numerical tests show that the weighted-BMP approach outperforms the Reverse Cuthill-McKee (RCM) algorithm.
• Score: 41.94295877935867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces weighted-BMP, a variant of the Bandwidth Minimization Problem (BMP), with a significant application in optimizing quantum emulation. Weighted-BMP optimizes particles ordering to reduce the emulation costs, by designing a particle interaction matrix where strong interactions are placed as close as possible to the diagonal. We formulate the problem using a Mixed Integer Linear Program (MILP) and solve it to optimality with a state of the art solver. To strengthen our MILP model, we introduce symmetry-breaking inequalities and establish a lower bound. Through extensive numerical analysis, we examine the impacts of these enhancements on the solver's performance. The introduced reinforcements result in an average CPU time reduction of 25.61 percent. Additionally, we conduct quantum emulations of realistic instances. Our numerical tests show that the weighted-BMP approach outperforms the Reverse Cuthill-McKee (RCM) algorithm, an efficient heuristic used for site ordering tasks in quantum emulation, achieving an average memory storage reduction of 24.48 percent. From an application standpoint, this study is the first to apply an exact optimization method, weighted-BMP, that considers interactions for site ordering in quantum emulation pre-processing, and shows its crucial role in cost reduction. From an algorithmic perspective, it contributes by introducing important reinforcements and lays the groundwork for future research on further enhancements, particularly on strengthening the weak linear relaxation of the MILP.

Related papers

• Scalable circuit depth reduction in feedback-based quantum optimization with a quadratic approximation [0.6834295298053009]
  We propose a new feedback law for parameter determination by introducing the second-order approximation with respect to time interval. We demonstrate that our proposal significantly reduces circuit depth, with its linear scaling with the problem size smaller by more than an order of magnitude.
  arXiv  Detail & Related papers  (2024-07-25T06:44:41Z)
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor [0.0]
  This paper presents a new hybrid classical-quantum approach to solve Mixed Linear Programming (MILP) We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem (SP) Our MILP to QUBO conversion tightens the upper bounds of the involved continuous variables, positively impacting the required qubit count, and the convergence of the algorithm.
  arXiv  Detail & Related papers  (2024-02-08T15:33:09Z)
• Mitigating crosstalk and residual coupling errors in superconducting quantum processors using many-body localization [21.175964469657803]
  This study introduces a novel calibration scheme harnessing the principles of Many-Body Localization (MBL) Our MBL-based methodology emerges as a stalwart against noise, notably crosstalk and residual coupling errors. Not only does this approach provide a marked improvement in performance, particularly where specific residue couplings are present, but it also presents a more resource-efficient and cost-effective calibration process.
  arXiv  Detail & Related papers  (2023-10-10T13:36:09Z)
• On-Chip Hardware-Aware Quantization for Mixed Precision Neural Networks [52.97107229149988]
  We propose an On-Chip Hardware-Aware Quantization framework, performing hardware-aware mixed-precision quantization on deployed edge devices. For efficiency metrics, we built an On-Chip Quantization Aware pipeline, which allows the quantization process to perceive the actual hardware efficiency of the quantization operator. For accuracy metrics, we propose Mask-Guided Quantization Estimation technology to effectively estimate the accuracy impact of operators in the on-chip scenario.
  arXiv  Detail & Related papers  (2023-09-05T04:39:34Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models [9.727062803700264]
  We introduce LUT-GEMM, an efficient kernel for quantized matrix multiplication. LUT-GEMM eliminates the resource-intensive dequantization process and reduces computational costs. We show experimentally that when applied to the OPT-175B model with 3-bit quantization, LUT-GEMM substantially accelerates token generation latency.
  arXiv  Detail & Related papers  (2022-06-20T03:48:17Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks. In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
  arXiv  Detail & Related papers  (2022-03-26T20:37:14Z)
• Fairly Constricted Multi-Objective Particle Swarm Optimization [0.0]
  We extend the state of the art Multi-objective optimization (MOO) solver, SMPSO, by incorporating exponentially-averaged momentum (EM) in it. The proposed solver matches the performance of SMPSO across the ZDT, DTLZ and WFG problem suites and even outperforms it in certain instances.
  arXiv  Detail & Related papers  (2021-04-10T14:39:59Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  Federated learning (FL) is vulnerable to external attacks on FL models during parameters transmissions. In this paper, we propose effective MP algorithms to combat state-of-the-art defensive aggregation mechanisms. Our experimental results demonstrate that the proposed CMP algorithms are effective and substantially outperform existing attack mechanisms.
  arXiv  Detail & Related papers  (2021-01-28T03:28:18Z)
• 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)

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.