Quantifiable simulation of quantum computation beyond stochastic ensemble computation
arXiv:1604.07517 · doi:10.1002/qute.201800037
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.
arXiv comment8 pages, 4 figures, Advanced Quantum Technologies (2018)
References in corpus (11)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Grover's quantum searching algorithm is optimal
- Information and Computation: Classical and Quantum Aspects
- The Communication Cost of Simulating Bell Correlations
- The General Quantum Interference Principle and the Duality Computer
- Condition for macroscopic realism beyond the Leggett-Garg inequalities
- Phase matching in quantum searching
- Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
- Non-classicality of temporal correlations