Boolean Hierarchical Tucker Networks on Quantum Annealers
- URL: http://arxiv.org/abs/2103.07399v1
- Date: Fri, 12 Mar 2021 16:45:58 GMT
- Title: Boolean Hierarchical Tucker Networks on Quantum Annealers
- Authors: Elijah Pelofske, Georg Hahn, Daniel O'Malley, Hristo N. Djidjev, Boian
S. Alexandrov
- Abstract summary: We investigate the capabilities of the quantum annealers of D-Wave Systems, Inc.
We show that BHTN can be calculated as a sequence of optimization problems suitable for the D-Wave 2000Q quantum annealer.
Although current technology is still fairly restricted in the problems they can address, we show that a complex problem such as BHTN can be solved efficiently and accurately.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealing is an emerging technology with the potential to solve some
of the computational challenges that remain unresolved as we approach an era
beyond Moore's Law. In this work, we investigate the capabilities of the
quantum annealers of D-Wave Systems, Inc., for computing a certain type of
Boolean tensor decomposition called Boolean Hierarchical Tucker Network (BHTN).
Boolean tensor decomposition problems ask for finding a decomposition of a
high-dimensional tensor with categorical, [true, false], values, as a product
of smaller Boolean core tensors. As the BHTN decompositions are usually not
exact, we aim to approximate an input high-dimensional tensor by a product of
lower-dimensional tensors such that the difference between both is minimized in
some norm. We show that BHTN can be calculated as a sequence of optimization
problems suitable for the D-Wave 2000Q quantum annealer. Although current
technology is still fairly restricted in the problems they can address, we show
that a complex problem such as BHTN can be solved efficiently and accurately.
Related papers
- Large-scale quantum annealing simulation with tensor networks and belief propagation [0.0]
We show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000qubit gates.
For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states.
For degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states.
arXiv Detail & Related papers (2024-09-18T18:00:08Z) - 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 Bayesian Optimization [64.58749619145908]
We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm.
It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting.
Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
arXiv Detail & Related papers (2023-10-09T03:10:42Z) - Efficient MILP Decomposition in Quantum Computing for ReLU Network
Robustness [2.854196251981274]
In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP)
We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach.
Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
arXiv Detail & Related papers (2023-04-30T13:10:56Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem.
The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment.
We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
arXiv Detail & Related papers (2022-04-18T21:45:13Z) - Post-Error Correction for Quantum Annealing Processor using
Reinforcement Learning [9.267156820352996]
We show how to correct states output by quantum annealers using reinforcement learning.
Our preliminary results show how to correct states output by quantum annealers using reinforcement learning.
arXiv Detail & Related papers (2022-03-03T21:31:06Z) - Quantum Annealing Algorithms for Boolean Tensor Networks [0.0]
We introduce and analyze three general algorithms for Boolean tensor networks.
We show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer.
We demonstrate that tensor with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.
arXiv Detail & Related papers (2021-07-28T22:38:18Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
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.