Can a stochastic ensemble computing machine imitate quantum computation
Jeongho Bang, Junghee Ryu, Chang-Woo Lee, Ki Hyuk Yee, Jinhyoung Lee, Wonmin Son · arXiv (Cornell University) · 2016
Where do classical and quantum computers fit in? or what can and cannot they do? have been long-standing questions. In particular, drawing a clear borderline between classical and quantum computations is obscure and still remains controversial. With this issue in mind, we attempt to find a qualitatively distinguishable feature of quantum computation (QC) in which QC is a superset of currently known classes of classical probabilistic computation. The main approach for our study is to consider a seemingly powerful classical computing machine called a stochastic ensemble machine (SEnM), which runs with an {\em ensemble} consisting of finite (even infinite, in principle) copies of a single probabilistic machine, e.g., a probabilistic Turing machine (PTM). Then, we assume and test the following hypothesis: there exists an SEnM imitating QC. The test is carried out by introducing an information-theoretic inequality that we call the readout inequality. This inequality is obeyed by every SEnM computation and also imposes a critical condition on QC: if the hypothesis holds, the inequality should be satisfied by QC for the SEnM imitating it. However, QC can violate the inequality, and the above hypothesis is generally not accepted. Noting that quantum Turing machine can cover an SEnM and thinking of SEnM $\supseteq$ PTM in our context, we conclude that QC is characterized beyond any classical probabilistic computation in the qualitative sense.