Improved separation between quantum and classical computers for sampling and functional tasks

• URL: http://arxiv.org/abs/2410.20935v1
• Date: Mon, 28 Oct 2024 11:30:10 GMT
• Title: Improved separation between quantum and classical computers for sampling and functional tasks
• Authors: Simon C. Marshall, Scott Aaronson, Vedran Dunjko,
• Abstract summary: 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.
• Score: 3.618534280726541
• License:
• Abstract: This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, 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 polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.

Related papers

• Quantum Circuit Learning on NISQ Hardware [0.0]
  Current quantum computers are small and error-prone systems. Fault-tolerant quantum computers are not expected to be available in the near future. We show that exemplary QCL circuits with up to three qubits are executable on the IBM quantum computer.
  arXiv  Detail & Related papers  (2024-05-03T13:00:32Z)
• The hardness of quantum spin dynamics [1.1999555634662633]
  We show that sampling from the output distribution generated by a wide class of quantum spin Hamiltonians is a hard problem for classical computers. We estimate that an instance involving about 200 spins will be challenging for classical devices but feasible for intermediate-scale quantum computers with fault-tolerant qubits.
  arXiv  Detail & Related papers  (2023-12-12T19:00:03Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• BQP is not in NP [0.0]
  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.
  arXiv  Detail & Related papers  (2022-09-19T23:17:57Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• 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)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Resource-Efficient Quantum Computing by Breaking Abstractions [9.695745674863554]
  Current quantum software stacks follow a layered approach similar to the stack of classical computers. In this review, we point out that greater efficiency of quantum computing systems can be achieved by breaking the abstractions between these layers.
  arXiv  Detail & Related papers  (2020-10-30T18:18:23Z)
• 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.