Details
| Original language | English |
|---|---|
| Article number | 140505 |
| Journal | Physical review letters |
| Volume | 112 |
| Issue number | 14 |
| Publication status | Published - 9 Apr 2014 |
| Externally published | Yes |
Abstract
Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multiqubit quantum state. It is computationally equivalent to the circuit model. Unlike the circuit model, however, its classical analog is little studied. Here we present a classical analog of MBQC whose computational complexity presents a rich structure. To do so, we identify uniform families of quantum computations [refining the circuits introduced by Bremner Proc. R. Soc. A 467, 459 (2010)] whose output is likely hard to exactly simulate (sample) classically. We demonstrate that these circuit families can be efficiently implemented in the MBQC model without adaptive measurement and, thus, can be achieved in a classical analog of MBQC whose resource state is a probability distribution which has been created quantum mechanically. Such states (by definition) violate no Bell inequality, but, if widely held beliefs about computational complexity are true, they, nevertheless, exhibit nonclassicality when used as a computational resource - an imprint of their quantum origin.
ASJC Scopus subject areas
- Physics and Astronomy(all)
- General Physics and Astronomy
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Physical review letters, Vol. 112, No. 14, 140505, 09.04.2014.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Measurement-Based Classical Computation
AU - Hoban, Matty J.
AU - Wallman, Joel J.
AU - Anwar, Hussain
AU - Usher, Naïri
AU - Raussendorf, Robert
AU - Browne, Dan E.
PY - 2014/4/9
Y1 - 2014/4/9
N2 - Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multiqubit quantum state. It is computationally equivalent to the circuit model. Unlike the circuit model, however, its classical analog is little studied. Here we present a classical analog of MBQC whose computational complexity presents a rich structure. To do so, we identify uniform families of quantum computations [refining the circuits introduced by Bremner Proc. R. Soc. A 467, 459 (2010)] whose output is likely hard to exactly simulate (sample) classically. We demonstrate that these circuit families can be efficiently implemented in the MBQC model without adaptive measurement and, thus, can be achieved in a classical analog of MBQC whose resource state is a probability distribution which has been created quantum mechanically. Such states (by definition) violate no Bell inequality, but, if widely held beliefs about computational complexity are true, they, nevertheless, exhibit nonclassicality when used as a computational resource - an imprint of their quantum origin.
AB - Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multiqubit quantum state. It is computationally equivalent to the circuit model. Unlike the circuit model, however, its classical analog is little studied. Here we present a classical analog of MBQC whose computational complexity presents a rich structure. To do so, we identify uniform families of quantum computations [refining the circuits introduced by Bremner Proc. R. Soc. A 467, 459 (2010)] whose output is likely hard to exactly simulate (sample) classically. We demonstrate that these circuit families can be efficiently implemented in the MBQC model without adaptive measurement and, thus, can be achieved in a classical analog of MBQC whose resource state is a probability distribution which has been created quantum mechanically. Such states (by definition) violate no Bell inequality, but, if widely held beliefs about computational complexity are true, they, nevertheless, exhibit nonclassicality when used as a computational resource - an imprint of their quantum origin.
UR - http://www.scopus.com/inward/record.url?scp=84898470712&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1304.2667
DO - 10.48550/arXiv.1304.2667
M3 - Article
AN - SCOPUS:84898470712
VL - 112
JO - Physical review letters
JF - Physical review letters
SN - 0031-9007
IS - 14
M1 - 140505
ER -