Solving systems of Boolean multivariate equations with quantum annealing

• URL: http://arxiv.org/abs/2111.13224v2
• Date: Tue, 8 Feb 2022 07:00:24 GMT
• Title: Solving systems of Boolean multivariate equations with quantum annealing
• Authors: Sergi Ramos-Calderer, Carlos Bravo-Prieto, Ruge Lin, Emanuele Bellini, Marc Manzano, Najwa Aaraj and Jos\'e I. Latorre
• Abstract summary: Polynomial systems over the binary field have important applications in cryptography, coding theory, and computer algebra. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. We design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space.
• Score: 1.1699027359021665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based post-quantum cryptography, coding theory, and computer algebra. In this work, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the Multivariate Quadratic problem. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources. Moreover, we design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space. Finally, we use D-Wave devices to successfully implement our methodologies on several instances of the Multivariate Quadratic problem.

Related papers

• On variants of multivariate quantum signal processing and their characterizations [0.0]
  Quantum signal processing (QSP) is a highly successful algorithmic primitive in quantum computing. We show that Haah's characterization of general QSP can be extended to homogeneous bivariable (commuting) quantum signal processing. We also show a similar result for an alternative inhomogeneous variant when the degree in one of the variables is at most 1, but construct a counterexample where both variables have degree 2.
  arXiv  Detail & Related papers  (2023-12-14T16:06:58Z)
• Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
  We present an algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and Quadratic Unconstrained Discrete Optimization (QUDO) problems with one-neighbor interactions. Our method is based on the simulation of a quantum state to which we will apply an imaginary time evolution and perform a series of partial traces to obtain the state of maximum amplitude.
  arXiv  Detail & Related papers  (2023-09-19T10:45:15Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Depth analysis of variational quantum algorithms for heat equation [0.0]
  We consider three approaches to solve the heat equation on a quantum computer. An exponential number of Pauli products in the Hamiltonian decomposition does not allow for the quantum speed up to be achieved. The ansatz tree approach exploits an explicit form of the matrix what makes it possible to achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2022-12-23T14:46:33Z)
• Quantum Kernel Methods for Solving Differential Equations [21.24186888129542]
  We propose several approaches for solving differential equations (DEs) with quantum kernel methods. We compose quantum models as weighted sums of kernel functions, where variables are encoded using feature maps and model derivatives are represented.
  arXiv  Detail & Related papers  (2022-03-16T18:56:35Z)
• Quantum variational PDE solver with machine learning [0.0]
  We propose a quantum variational (QuVa) PDE solver with the aid of machine learning (ML) schemes. The core quantum processing in this solver is to calculate efficiently the expectation value of specially designed quantum operators.
  arXiv  Detail & Related papers  (2021-09-19T20:30:02Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods [1.802439717192088]
  We explore utilizing quantum computers for the purpose of solving differential equations. We devise and simulate corresponding digital quantum circuits, and implement and run a 6$mathrmth$ order Gauss-Legendre collocation method. As promising future scenario, the digital arithmetic method could be employed as an "oracle" within quantum search algorithms for inverse problems.
  arXiv  Detail & Related papers  (2020-12-17T09:49:35Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)
• Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
  We review and extend the application of deep learning to quantum geometric control problems. We demonstrate enhancements in time-optimal control in the context of quantum circuit synthesis problems. Our results are of interest to researchers in quantum control and quantum information theory seeking to combine machine learning and geometric techniques for time-optimal control problems.
  arXiv  Detail & Related papers  (2020-06-19T19:12:14Z)

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.