Multi-layer quantum search and inclusion of NP into BQP

• URL: http://arxiv.org/abs/2004.11347v2
• Date: Sat, 25 Apr 2020 11:16:14 GMT
• Title: Multi-layer quantum search and inclusion of NP into BQP
• Authors: Shan Jin, Xiaoting Wang, Bo Li
• Abstract summary: We present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. Our results show that the speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated.
• Score: 6.362434591714693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. As direct applications, any NP problems can be solved efficiently on a quantum circuit with only polynomial gate complexity. In particular, such multi-layer search can solve the factoring problem with an exponential speedup, providing an alternative to Shor's algorithm. Our results show that the exponential speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated. With no contradiction to the quadratic optimality of single-layer query complexity, the great potential of Grover's search is fully released by such multi-layer search design.

Related papers

• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  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''
  arXiv  Detail & Related papers  (2024-07-24T22:06:05Z)
• QArchSearch: A Scalable Quantum Architecture Search Package [1.725192300740999]
  We present textttQArchSearch, an AI based quantum architecture search package with the textttQTensor library as a backend. We show that the search package is able to efficiently scale the search to large quantum circuits and enables the exploration of more complex models for different quantum applications.
  arXiv  Detail & Related papers  (2023-10-11T20:00:33Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• 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)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
  arXiv  Detail & Related papers  (2020-09-11T17:31:39Z)
• Hybrid divide-and-conquer approach for tree search algorithms [0.0]
  We study the hybrid divide-and-conquer method in the context of tree search algorithms. We provide conditions for speedups for the well known algorithm of DPLL. We briefly discuss the limitations of hybrid methods in providing speed-ups for larger problems.
  arXiv  Detail & Related papers  (2020-07-14T13:57:12Z)

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.