Quantifiable Simulation of Quantum Computation beyond Stochastic Ensemble Computation. Issue 2 (24th August 2018)

• Record Type: Journal Article
• Authors: Bang, Jeongho; Ryu, Junghee; Lee, Chang‐Woo; Yee, Ki Hyuk; Lee, Jinhyoung; Son, Wonmin
• Is Part Of: Advanced quantum technologies. Volume 1:Issue 2(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-08-24
• Subjects: probabilistic Turing machine -- stochastic ensemble computation -- quantum computation -- quantum Turing machine; Quantum theory -- Periodicals; Quantum computing -- Periodicals; Quantum chemistry -- Periodicals; Quantum electronics -- Periodicals; 537.5
• DOI: 10.1002/qute.201800037
• Languages: English
• ISSNs: 2511-9044

Abstract

Abstract: In this study, a distinctive feature of quantum computation (QC) is characterized. To this end, a seemingly‐powerful classical computing model, called "stochastic ensemble machine (SEnM), " is considered. The SEnM runs with an ensemble consisting of finite copies of a single probabilistic machine, hence is as powerful as a probabilistic Turing machine (PTM). Then the hypothesis—that is, the SEnM can effectively simulate a general circuit model of QC—is tested by introducing an information‐theoretic inequality, named readout inequality. The inequality is satisfied by the SEnM and imposes a critical condition: if the hypothesis holds, the inequality should be satisfied by the probing model of QC. However, it is shown that the above hypothesis is not generally accepted with the inequality violation; namely, such a simulation necessarily fails, implying that PTM ⊆ QC. Abstract : A model of quantum computation (QC) is compared with a generalized classical computation model, named stochastic ensemble computation (SEnC). SEnC runs in an ensemble consisting of finite copies of single probabilistic entities, and hence is a generalized probabilistic Turing machine. Impossibility of simulating a QC in the SEnC is proved, manifesting "QC is characterized beyond any classical probabilistic computation."