Please use this identifier to cite or link to this item:
https://doi.org/10.1038/s41534-018-0103-1
DC Field | Value | |
---|---|---|
dc.title | Quantum superiority for verifying NP-complete problems with linear optics | |
dc.contributor.author | Arrazola, J.M. | |
dc.contributor.author | Diamanti, E. | |
dc.contributor.author | Kerenidis, I. | |
dc.date.accessioned | 2021-12-09T04:59:14Z | |
dc.date.available | 2021-12-09T04:59:14Z | |
dc.date.issued | 2018 | |
dc.identifier.citation | Arrazola, J.M., Diamanti, E., Kerenidis, I. (2018). Quantum superiority for verifying NP-complete problems with linear optics. npj Quantum Information 4 (1) : 56. ScholarBank@NUS Repository. https://doi.org/10.1038/s41534-018-0103-1 | |
dc.identifier.issn | 2056-6387 | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/210077 | |
dc.description.abstract | Demonstrating quantum superiority for some computational task will be a milestone for quantum technologies and would show that computational advantages are possible not only with a universal quantum computer but with simpler physical devices. Linear optics is such a simpler but powerful platform where classically-hard information processing tasks, such as Boson Sampling, can be in principle implemented. In this work, we study a fundamentally different type of computational task to achieve quantum superiority using linear optics, namely the task of verifying NP-complete problems. We focus on a protocol by Aaronson et al. (2008) that uses quantum proofs for verification. We show that the proof states can be implemented in terms of a single photon in an equal superposition over many optical modes. Similarly, the tests can be performed using linear-optical transformations consisting of a few operations: a global permutation of all modes, simple interferometers acting on at most four modes, and measurement using single-photon detectors. We also show that the protocol can tolerate experimental imperfections. © 2018, The Author(s). | |
dc.publisher | Nature Partner Journals | |
dc.rights | Attribution 4.0 International | |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
dc.source | Scopus OA2018 | |
dc.type | Article | |
dc.contributor.department | CENTRE FOR QUANTUM TECHNOLOGIES | |
dc.description.doi | 10.1038/s41534-018-0103-1 | |
dc.description.sourcetitle | npj Quantum Information | |
dc.description.volume | 4 | |
dc.description.issue | 1 | |
dc.description.page | 56 | |
Appears in Collections: | Staff Publications Elements |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
10_1038_s41534-018-0103-1.pdf | 957.02 kB | Adobe PDF | OPEN | None | View/Download |
This item is licensed under a Creative Commons License