Experimental demonstration of quantum advantage for NP verification with
limited information
- URL: http://arxiv.org/abs/2007.15876v2
- Date: Mon, 8 Feb 2021 10:38:40 GMT
- Title: Experimental demonstration of quantum advantage for NP verification with
limited information
- Authors: Federico Centrone, Niraj Kumar, Eleni Diamanti, Iordanis Kerenidis
- Abstract summary: We show an experimental demonstration of a quantum computational advantage in a prover-verifier interactive setting.
We provide a simple linear optical implementation that can perform this verification task efficiently.
We also provide strong evidence that, fixing the size of the proof, a classical computer would take much longer time.
- Score: 4.6453787256723365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent years, many computational tasks have been proposed as candidates
for showing a quantum computational advantage, that is an advantage in the time
needed to perform the task using a quantum instead of a classical machine.
Nevertheless, practical demonstrations of such an advantage remain particularly
challenging because of the difficulty in bringing together all necessary
theoretical and experimental ingredients. Here, we show an experimental
demonstration of a quantum computational advantage in a prover-verifier
interactive setting, where the computational task consists in the verification
of an NP-complete problem by a verifier who only gets limited information about
the proof sent by an untrusted prover in the form of a series of unentangled
quantum states. We provide a simple linear optical implementation that can
perform this verification task efficiently (within a few seconds), while we
also provide strong evidence that, fixing the size of the proof, a classical
computer would take much longer time (assuming only that it takes exponential
time to solve an NP-complete problem). While our computational advantage
concerns a specific task in a scenario of mostly theoretical interest, it
brings us a step closer to potential useful applications, such as server-client
quantum computing.
Related papers
- Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
We present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems.
We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
arXiv Detail & Related papers (2023-11-16T16:11:44Z) - Hybrid quantum transfer learning for crack image classification on NISQ
hardware [62.997667081978825]
We present an application of quantum transfer learning for detecting cracks in gray value images.
We compare the performance and training time of PennyLane's standard qubits with IBM's qasm_simulator and real backends.
arXiv Detail & Related papers (2023-07-31T14:45:29Z) - Classical Verification of Quantum Learning [42.362388367152256]
We develop a framework for classical verification of quantum learning.
We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples.
Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
arXiv Detail & Related papers (2023-06-08T00:31:27Z) - 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) - Experimental Implementation of an Efficient Test of Quantumness [49.588006756321704]
A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior.
Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification.
arXiv Detail & Related papers (2022-09-28T18:00: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) - Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
We present an approach where the quantum computation is supplemented by a classical result.
Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative.
In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
arXiv Detail & Related papers (2022-09-12T15:47:44Z) - Quantum reservoir computation utilising scale-free networks [0.0]
We introduce a new reservoir computational model for pattern recognition showing a quantum advantage utilizing scale-free networks.
The simplicity in our approach illustrates the computational power in quantum complexity as well as provide new applications for such processors.
arXiv Detail & Related papers (2021-08-27T06:28:08Z) - On exploring practical potentials of quantum auto-encoder with
advantages [92.19792304214303]
Quantum auto-encoder (QAE) is a powerful tool to relieve the curse of dimensionality encountered in quantum physics.
We prove that QAE can be used to efficiently calculate the eigenvalues and prepare the corresponding eigenvectors of a high-dimensional quantum state.
We devise three effective QAE-based learning protocols to solve the low-rank state fidelity estimation, the quantum Gibbs state preparation, and the quantum metrology tasks.
arXiv Detail & Related papers (2021-06-29T14:01:40Z) - Simpler Proofs of Quantumness [16.12500804569801]
A proof of quantumness is a method for provably demonstrating that a quantum device can perform computational tasks that a classical device cannot.
There are currently three approaches for exhibiting proofs of quantumness.
We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function.
arXiv Detail & Related papers (2020-05-11T01:31:18Z) - Statistical Limits of Supervised Quantum Learning [90.0289160657379]
We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning cannot achieve polylogarithmic runtimes in the input dimension.
We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most speedups over efficient classical algorithms.
arXiv Detail & Related papers (2020-01-28T17:35:32Z)
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.