Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2406.13412 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms

Valter Uotila

Published Sep 15, 2024• 2 citations
arXivHTMLPDF

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.

DOI
10.1109/qce60285.2024.00053

Related papers

Quantum annealing algorithms for Boolean tensor networks

Elijah Pelofske, Georg Hahn, Daniel O’Malley +2 more

Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., [Formula: see text]) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor's with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

arXiv:2107.13659•Scientific Reports•May 20, 2022•18 citations

VeloxQ: A Fast and Efficient QUBO Solver

Jakub Pawłowski, Jan Tuziemski, Paweł Tarasiuk +5 more

We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to $10^{8}$ sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.

arXiv:2501.19221•Jan 31, 2025•2 citations

Tensorized Pauli decomposition algorithm

Lukas Hantzko, Lennart Binkowski, Sabhyata Gupta

Abstract This paper introduces a novel general-purpose algorithm for Pauli decomposition that employs matrix slicing and addition rather than expensive matrix multiplication, significantly accelerating the decomposition of multi-qubit matrices. In a detailed complexity analysis, we show that the algorithm admits the best known worst-case scaling and more favorable runtimes for many practical examples. Numerical experiments are provided to validate the asymptotic speed-up already for small instance sizes, underscoring the algorithm’s potential significance in the realm of quantum computing and quantum chemistry simulations.

Physica Scripta•Jul 17, 2024•27 citations

HUBO formulations for solving the eigenvalue problem

Kyungtaek Jun, Hyunju Lee

Solving the eigenvalue problem is particularly important in almost all fields of science and engineering. With the development of quantum computers, multiple algorithms have been proposed for this purpose. However, such methods are usually only applicable to matrices of specific types, such as unitary or Hermitian matrices. The quantum annealer of the D-Wave, a quantum computer, returns the minimum value of the quadratic unconstrained binary optimization (QUBO) model. Thus, quantum annealers can be leveraged to solve arbitrary eigenvalue problems by formulating corresponding QUBO models. In this paper, we propose two higher-order unconstrained optimization (HUBO) formulations to solve eigenvalue problems involving n×n general matrices. In addition, we use a formula to reduce the order and convert the HUBO model into a QUBO model. Further, by using a quantum approximate optimization algorithm, this method can be extended to a gate-model quantum computer.

Results in Control and Optimization•Mar 22, 2023•7 citations

Low-rank tensor decompositions of quantum circuits

Patrick Gelß, Stefan Klus, Knebel, Sebastian +2 more

Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the continuing rise in complexity, the development, simulation, optimization, and physical realization of quantum circuits is of utmost importance for designing novel algorithms. We show how matrix product states (MPSs) and matrix product operators (MPOs) can be used to express certain quantum states, quantum gates, and entire quantum circuits as low-rank tensors. This enables the analysis and simulation of complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. We present different examples to demonstrate the advantages of MPO formulations and show that they are more efficient than conventional techniques if the bond dimensions of the wave function representation can be kept small throughout the simulation.

arXiv:2205.09882•May 19, 2022•1 citation

Tensor quantum programming

A. Termanova, Artem A. Melnikov, Egor Mamenchikov +6 more

Abstract Running quantum algorithms often involves implementing complex quantum circuits with such a large number of multi-qubit gates that the challenge of tackling practical applications appears daunting. In this article, we propose a novel approach called Tensor Quantum Programming, which leverages tensor networks (TNs) for hybrid quantum computing. Our key insight is that the primary challenge of algorithms based on TNs lies in their high ranks (bond dimensions). Quantum computing offers a potential solution to this challenge, as an ideal quantum computer can represent tensors with arbitrarily high ranks in contrast to classical counterparts, which indicates the way towards quantum advantage. While tensor-based vector-encoding and state-readout are known procedures, the matrix-encoding required for performing matrix-vector multiplications directly on quantum devices is much less studied. We introduce an algorithm that encodes matrix product operators into quantum circuits with a depth that scales linearly with the number of qubits. We demonstrate the algorithm’s performance for matrices commonly encountered in differential equations, optimization problems, and quantum chemistry, for systems involving up to 50 qubits.

arXiv:2403.13486•New Journal of Physics•Nov 28, 2024•7 citations
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.
Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., [Formula: see text]) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor's with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.
We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to 10810^{8}108 sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.
Abstract This paper introduces a novel general-purpose algorithm for Pauli decomposition that employs matrix slicing and addition rather than expensive matrix multiplication, significantly accelerating the decomposition of multi-qubit matrices. In a detailed complexity analysis, we show that the algorithm admits the best known worst-case scaling and more favorable runtimes for many practical examples. Numerical experiments are provided to validate the asymptotic speed-up already for small instance sizes, underscoring the algorithm’s potential significance in the realm of quantum computing and quantum chemistry simulations.
Solving the eigenvalue problem is particularly important in almost all fields of science and engineering. With the development of quantum computers, multiple algorithms have been proposed for this purpose. However, such methods are usually only applicable to matrices of specific types, such as unitary or Hermitian matrices. The quantum annealer of the D-Wave, a quantum computer, returns the minimum value of the quadratic unconstrained binary optimization (QUBO) model. Thus, quantum annealers can be leveraged to solve arbitrary eigenvalue problems by formulating corresponding QUBO models. In this paper, we propose two higher-order unconstrained optimization (HUBO) formulations to solve eigenvalue problems involving n×n general matrices. In addition, we use a formula to reduce the order and convert the HUBO model into a QUBO model. Further, by using a quantum approximate optimization algorithm, this method can be extended to a gate-model quantum computer.
Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the continuing rise in complexity, the development, simulation, optimization, and physical realization of quantum circuits is of utmost importance for designing novel algorithms. We show how matrix product states (MPSs) and matrix product operators (MPOs) can be used to express certain quantum states, quantum gates, and entire quantum circuits as low-rank tensors. This enables the analysis and simulation of complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. We present different examples to demonstrate the advantages of MPO formulations and show that they are more efficient than conventional techniques if the bond dimensions of the wave function representation can be kept small throughout the simulation.
Abstract Running quantum algorithms often involves implementing complex quantum circuits with such a large number of multi-qubit gates that the challenge of tackling practical applications appears daunting. In this article, we propose a novel approach called Tensor Quantum Programming, which leverages tensor networks (TNs) for hybrid quantum computing. Our key insight is that the primary challenge of algorithms based on TNs lies in their high ranks (bond dimensions). Quantum computing offers a potential solution to this challenge, as an ideal quantum computer can represent tensors with arbitrarily high ranks in contrast to classical counterparts, which indicates the way towards quantum advantage. While tensor-based vector-encoding and state-readout are known procedures, the matrix-encoding required for performing matrix-vector multiplications directly on quantum devices is much less studied. We introduce an algorithm that encodes matrix product operators into quantum circuits with a depth that scales linearly with the number of qubits. We demonstrate the algorithm’s performance for matrices commonly encountered in differential equations, optimization problems, and quantum chemistry, for systems involving up to 50 qubits.