Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Lasers and Electro-Optics

Experimental demonstration of quantum advantage for NP verification

Federico Centrone, Niraj Kumar, Eleni Diamanti, Iordanis Kerenidis

Published Jan 1, 2021• 0 citations
Publisher

Abstract

We showcase the power of linear optics through the implementation of a quantum protocol with coherent states. Our work provides evidence for a computational quantum advantage in the interactive setting, drawing near potentially useful applications.
DOI
10.1364/cleo_qels.2021.fth2n.5

Related papers

Experimental demonstration of quantum leader election in linear optics

Yuta Okubo, Xiang‐Bin Wang, Akihisa Tomita

We propose and demonstrate a new implementation of a quantum protocol which can operate deterministically only with linear optics. This protocol, which is called quantum leader election, exhibits the quantum advantages over classical protocol.

Frontiers in Optics•Jan 1, 2007•1 citation

Experimental demonstration of quantum advantage for NP verification with limited information

Federico Centrone, Niraj Kumar, Eleni Diamanti +1 more

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.

arXiv:2007.15876•Nature Communications•Feb 8, 2021•19 citations

Quantum computation with coherent states

Alexei Gilchrist, Timothy C. Ralph, William J. Munro +1 more

We extend a previous proposal for performing deterministic quantum computation using coherent states and linear optics by examining a new version of one of the gates which offers several advantages.

•Jan 1, 2003•7 citations

Demonstration of Interactive Protocols for Classically-Verifiable Quantum Advantage

Daiwei Zhu, Crystal Noel, Andrew Risinger +12 more

Bulletin of the American Physical Society•Jun 1, 2021•2 citations

Experimental demonstration of quantum advantage for one-way communication complexity surpassing best-known classical protocol

Niraj Kumar, Iordanis Kerenidis, Eleni Diamanti

Demonstrating a quantum advantage with currently available experimental systems is of utmost importance in quantum information science. While this remains elusive for quantum computation, the field of communication complexity offers the possibility to already explore and showcase this advantage for useful tasks. Here, we define such a task, the Sampling Matching problem, which is inspired by the Hidden Matching problem and features an exponential gap between quantum and classical protocols in the one-way communication model. Our problem allows by its conception a photonic implementation based on encoding in the phase of coherent states of light, the use of a fixed size linear optic circuit, and single-photon detection. This enables us to demonstrate in a proof-of-principle experiment an advantage in the transmitted information resource over the best known classical protocol, something impossible to reach for the original Hidden Matching problem. Our demonstration has implications in quantum verification and cryptographic settings.

arXiv:1811.09154•Nature Communications•Sep 12, 2019•26 citations

Experimental implementation of efficient linear optics quantum computation

Jeremy L. O’Brien, Geoff J. Pryde, TB Bell +3 more

•Jan 1, 2002•0 citations
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.
Demonstrating a quantum advantage with currently available experimental systems is of utmost importance in quantum information science. While this remains elusive for quantum computation, the field of communication complexity offers the possibility to already explore and showcase this advantage for useful tasks. Here, we define such a task, the Sampling Matching problem, which is inspired by the Hidden Matching problem and features an exponential gap between quantum and classical protocols in the one-way communication model. Our problem allows by its conception a photonic implementation based on encoding in the phase of coherent states of light, the use of a fixed size linear optic circuit, and single-photon detection. This enables us to demonstrate in a proof-of-principle experiment an advantage in the transmitted information resource over the best known classical protocol, something impossible to reach for the original Hidden Matching problem. Our demonstration has implications in quantum verification and cryptographic settings.