Tensor networks based quantum optimization algorithm

• URL: http://arxiv.org/abs/2404.15048v1
• Date: Tue, 23 Apr 2024 13:49:11 GMT
• Title: Tensor networks based quantum optimization algorithm
• Authors: V. Akshay, Ar. Melnikov, A. Termanova, M. R. Perelshtein,
• Abstract summary: In optimization, one of the well-known classical algorithms is power iterations. We propose a quantum realiziation to circumvent this pitfall. Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In optimization, one of the well-known classical algorithms is power iterations. Simply stated, the algorithm recovers the dominant eigenvector of some diagonalizable matrix. Since numerous optimization problems can be formulated as an eigenvalue/eigenvector search, this algorithm features wide applicability. Operationally, power iterations consist of performing repeated matrix-to-vector multiplications (or MatVec) followed by a renormilization step in order to converge to the dominant eigenvalue/eigenvector. However, classical realizations, including novel tensor network based approaches, necessitate an exponential scaling for the algorithm's run-time. In this paper, we propose a quantum realiziation to circumvent this pitfall. Our methodology involves casting low-rank representations; Matrix Product Operators (MPO) for matrices and Matrix Product States (MPS) for vectors, into quantum circuits. Specifically, we recover a unitary approximation by variationally minimizing the Frobenius distance between a target MPO and an MPO ansatz wherein the tensor cores are constrained to unitaries. Such an unitary MPO can easily be implemented as a quantum circuit with the addition of ancillary qubits. Thereafter, with appropriate initialization and post-selection on the ancillary space, we realize a single iteration of the classical algorithm. With our proposed methodology, power iterations can be realized entirely on a quantum computer via repeated, static circuit blocks; therefore, a run-time advantage can indeed be guaranteed. Moreover, by exploiting Riemannian optimization and cross-approximation techniques, our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.

Related papers

• Quantum Circuit Optimization using Differentiable Programming of Tensor Network States [0.0]
  The said algorithm runs on classical hardware and finds shallow, accurate quantum circuits. All circuits achieve high state fidelities within reasonable CPU time and modest memory requirements.
  arXiv  Detail & Related papers  (2024-08-22T17:48:53Z)
• Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms [1.5540058359482858]
  We focus on discovering practical matrix multiplication algorithms and develop two algorithms to compute decompositions on quantum computers. The algorithms are expressed as higher-order unconstrained binary optimization (HUBO) problems. We show that by fixing a shorter length than the length for the best-known decomposition, we can ensure that the solution to the holistic optimization problem would yield faster matrix multiplication algorithms.
  arXiv  Detail & Related papers  (2024-06-19T10:05:57Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• A doubly stochastic matrices-based approach to optimal qubit routing [0.0]
  Swap mapping is a quantum compiler optimization that, by SWAP gates, maps a logical quantum circuit to an equivalent physically implementable one. In this work, we employ a structure called doubly convex matrix, which is defined as a combination of permutation matrices. We show that the proposed algorithm, at the cost of additional time, can deliver significant depth reduction when compared to the state of the art algorithm SABRE.
  arXiv  Detail & Related papers  (2022-11-14T09:25:35Z)
• Quantum Algorithm For Estimating Eigenvalue [0.0]
  We provide a quantum algorithm for estimating the largest eigenvalue in magnitude of a given Hermitian matrix. Our quantum procedure can also yield exponential speedup compared to classical algorithms that solve the same problem.
  arXiv  Detail & Related papers  (2022-11-11T13:02:07Z)
• Automatic and effective discovery of quantum kernels [43.702574335089736]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data. We present a different approach, which employs optimization techniques, similar to those used in neural architecture search and AutoML. The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• 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)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03:52Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• 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.