Quantum computational advantage implies contextuality

• URL: http://arxiv.org/abs/2112.00024v2
• Date: Wed, 15 Dec 2021 12:21:54 GMT
• Title: Quantum computational advantage implies contextuality
• Authors: Farid Shahandeh
• Abstract summary: We show that a separation between the class of all problems that can efficiently be solved on a quantum computer and those using classical algorithms implies the time generalized contextuality of quantum algorithms. Our result subsumes versions of Gottesman-Knill theorem as special cases.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that a separation between the class of all problems that can efficiently be solved on a quantum computer and those solvable using probabilistic classical algorithms in polynomial time implies the generalized contextuality of quantum algorithms. Our result subsumes versions of Gottesman-Knill theorem as special cases.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Universal Euler-Cartan Circuits for Quantum Field Theories [0.0]
  A hybrid quantum-classical algorithm is presented for the computation of non-perturbative characteristics of quantum field theories. The algorithm relies on a universal parametrized quantum circuit ansatz based on Euler and Cartan's decompositions of single and two-qubit operators.
  arXiv  Detail & Related papers  (2024-07-31T01:59:09Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
  arXiv  Detail & Related papers  (2023-11-28T01:06:03Z)
• 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)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• 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)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum algorithmic differentiation [0.0]
  We present an algorithm to perform algorithmic differentiation in the context of quantum computing. We present two versions of the algorithm, one which is fully quantum and one which employees a classical step.
  arXiv  Detail & Related papers  (2020-06-23T22:52:22Z)

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.