Discretized Quantum Exhaustive Search for Variational Quantum Algorithms

• URL: http://arxiv.org/abs/2407.17659v1
• Date: Wed, 24 Jul 2024 22:06:05 GMT
• Title: Discretized Quantum Exhaustive Search for Variational Quantum Algorithms
• Authors: Dekel Meirom, Ittay Alfassi, Tal Mor,
• Abstract summary: Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers promise a great computational advantage over classical computers, yet currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. Variational Quantum Algorithms (VQAs) have emerged as a leading strategy to address these limitations by optimizing cost functions based on measurement results of shallow-depth circuits. However, the optimization process usually suffers from severe trainability issues as a result of the exponentially large search space, mainly local minima and barren plateaus. Here we propose a novel method that can improve variational quantum algorithms -- ``discretized quantum exhaustive search''. On classical computers, exhaustive search, also named brute force, solves small-size NP complete and NP hard problems. Exhaustive search and efficient partial exhaustive search help designing heuristics and exact algorithms for solving larger-size problems by finding easy subcases or good approximations. We adopt this method to the quantum domain, by relying on mutually unbiased bases for the $2^n$-dimensional Hilbert space. We define a discretized quantum exhaustive search that works well for small size problems. We provide an example of an efficient partial discretized quantum exhaustive search for larger-size problems, in order to extend classical tools to the quantum computing domain, for near future and far future goals. Our method enables obtaining intuition on NP-complete and NP-hard problems as well as on Quantum Merlin Arthur (QMA)-complete and QMA-hard problems. We demonstrate our ideas in many simple cases, providing the energy landscape for various problems and presenting two types of energy curves via VQAs.

Related papers

• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• A Quantum Algorithm Based Heuristic to Hide Sensitive Itemsets [1.8419202109872088]
  We present a quantum approach to solve a well-studied problem in the context of data sharing. We present results on experiments involving small datasets to illustrate how the problem could be solved using quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-12T20:44:46Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NP-hard problems are not believed to be exactly solvable through general time algorithms. In this paper, we build upon a proprietary methodology which logarithmically scales with problem size. These algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256.
  arXiv  Detail & Related papers  (2023-01-17T16:03:33Z)
• 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)
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing [1.7077661158850292]
  We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems. We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer. Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
  arXiv  Detail & Related papers  (2021-07-22T08:12:49Z)
• 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)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• 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.