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
- On quantum learning algorithms for noisy linear problems [0.6430989240829326]
Quantum algorithms have shown successful results in solving noisy linear problems with quantum samples.
New quantum and classical algorithms are presented under the same assumptions as in the earlier works.
arXiv Detail & Related papers (2024-04-05T07:35:06Z) - 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) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - 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.