BQP is not in NP

• URL: http://arxiv.org/abs/2209.10398v1
• Date: Mon, 19 Sep 2022 23:17:57 GMT
• Title: BQP is not in NP
• Authors: Jonah Librande
• Abstract summary: I show that quantum computation is able to efficiently solve problems far beyond the capabilities of classical computers. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.

Related papers

• Improved separation between quantum and classical computers for sampling and functional tasks [3.618534280726541]
  This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection. We prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the hierarchy collapses to its second level.
  arXiv  Detail & Related papers  (2024-10-28T11:30:10Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  There are problems for which there is no trivial' computational advantage possible with the current quantum hardware. We would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity? By the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT.
  arXiv  Detail & Related papers  (2023-09-28T13:30:20Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Relation between quantum advantage in supervised learning and quantum computational advantage [0.0]
  Recent work shows that computational and learning advantage are, in general, not equivalent. The existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions. Results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem.
  arXiv  Detail & Related papers  (2023-04-13T17:34:53Z)
• An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory [5.907281242647458]
  We prove that quantum computers feature an in-principle super-polynomial advantage over classical computers in approximating solutions to optimization problems. The core of the quantum advantage is ultimately borrowed from Shor's quantum algorithm for factoring.
  arXiv  Detail & Related papers  (2022-12-16T19:01:04Z)
• 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)
• Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
  We propose a resource allocation scheme for distributed quantum computing (DQC) based on programming to minimize the total deployment cost for quantum resources. The evaluation demonstrates the effectiveness and ability of the proposed scheme to balance the utilization of quantum computers and on-demand quantum computers.
  arXiv  Detail & Related papers  (2022-09-16T02:37:32Z)
• Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines [0.0]
  We show that variational quantum classifiers (VQC) and support vector machines with quantum kernels (QSVM) can solve a classification problem based on the k-Forrelation problem. Our results imply that there exists a feature map and a quantum kernel that make VQC and QSVM efficient solvers for any BQP problem.
  arXiv  Detail & Related papers  (2022-07-12T22:03:31Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem. The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
  arXiv  Detail & Related papers  (2020-05-06T14:18:44Z)

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.