Quantifiable Simulation of Quantum Computation beyond Stochastic Ensemble Computation. Issue 2 (24th August 2018) - Bang, Jeongho; Ryu, Junghee; Lee, Chang‐Woo; Yee, Ki Hyuk; Lee, Jinhyoung; Son, Wonmin
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."