Please use this identifier to cite or link to this item: https://doi.org/10.1038/s41534-018-0103-1
DC FieldValue
dc.titleQuantum superiority for verifying NP-complete problems with linear optics
dc.contributor.authorArrazola, J.M.
dc.contributor.authorDiamanti, E.
dc.contributor.authorKerenidis, I.
dc.date.accessioned2021-12-09T04:59:14Z
dc.date.available2021-12-09T04:59:14Z
dc.date.issued2018
dc.identifier.citationArrazola, 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.issn2056-6387
dc.identifier.urihttps://scholarbank.nus.edu.sg/handle/10635/210077
dc.description.abstractDemonstrating 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.publisherNature Partner Journals
dc.rightsAttribution 4.0 International
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.sourceScopus OA2018
dc.typeArticle
dc.contributor.departmentCENTRE FOR QUANTUM TECHNOLOGIES
dc.description.doi10.1038/s41534-018-0103-1
dc.description.sourcetitlenpj Quantum Information
dc.description.volume4
dc.description.issue1
dc.description.page56
Appears in Collections:Staff Publications
Elements

Show simple item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
10_1038_s41534-018-0103-1.pdf957.02 kBAdobe PDF

OPEN

NoneView/Download

SCOPUSTM   
Citations

8
checked on Dec 3, 2022

Page view(s)

66
checked on Dec 1, 2022

Google ScholarTM

Check

Altmetric


This item is licensed under a Creative Commons License Creative Commons