Quantum models of computation are widely believed to be more powerful than classical ones. Efforts center on proving that, for a given problem, quantum algorithms are more resource efficient than any classical one. All this, however, assumes a standard predictive paradigm of reasoning where, given initial conditions, the future holds the answer. How about bringing information from the future to the present and exploit it to one's advantage? This is a radical new approach for reasoning, so-called Retrodictive Computation, that benefits from the specific form of the computed functions. We demonstrate how to use tools of symbolic computation to realize retrodictive quantum computing at scale and exploit it to efficiently, and classically, solve instances of the quantum Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and Shor's algorithms.
翻译:量子计算模型被广泛认为比古典模型更强大。 努力中心在于证明对于某个问题来说,量子算法比古典算法更有效率。 然而,所有这一切假设了标准的预测推理范式,根据最初的条件,未来在其中占据着答案。 如何将信息从未来带到现在并利用它来为他人谋利? 这是一个全新的推理方法,即所谓的“逆向计算法 ”, 即从计算函数的具体形式中受益。 我们展示了如何使用符号计算工具实现规模反向量子计算,并有效地利用它,在典型情况下,解决德乌施-约兹萨、伯恩斯坦-瓦齐拉尼、西蒙、格罗弗和肖尔的算法案例。