Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms
arXiv:2406.13412 · doi:10.1109/QCE60285.2024.00053
Abstract
Quantum computing and modern tensor-based computing have a strong connection, which is especially demonstrated by simulating quantum computations with tensor networks. The other direction is less studied: quantum computing is not often applied to tensor-based problems. Considering tensor decompositions, 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, which are translated into quadratic unconstrained binary optimization (QUBO) problems. Our first algorithm is decompositional to keep the optimization problem feasible for the current quantum devices. Starting from a suitable initial point, the algorithm discovers tensor decomposition corresponding to the famous Strassen matrix multiplication algorithm, utilizing the current quantum annealers. Since the decompositional algorithm does not guarantee minimal length for found tensor decompositions, we develop a holistic algorithm that can find fixed-length decompositions. Theoretically, 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 comment12 pages, 6 figures
References in corpus (15)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- A variational eigenvalue solver on a quantum processor
- Ising formulations of many NP problems
- Noisy intermediate-scale quantum (NISQ) algorithms
- Adiabatic Quantum Computing
- Quantum Logic Gates in Optical Lattices
- Tensor networks for complex quantum systems
- Towards Quantum Machine Learning with Tensor Networks
- Hyper-optimized tensor network contraction
- Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- On the representation of Boolean and real functions as Hamiltonians for quantum computing
- Multivariable Optimization: Quantum Annealing & Computation
- Graph isomorphism and adiabatic quantum computing
- Tensors in computations