Journal Article

Oversimplifying quantum factoring

Vargo, Alexander, Smolin, John A., Smith, Graeme

2013

Overview

Building a device capable of factoring large numbers is a major goal of quantum computing; an algorithm for quantum factoring (Shor’s algorithm) exists, and a simple coin-tossing exercise is used to illustrate the dangers of oversimplification when implementing this algorithm experimentally. A cautionary approach to quantum computing Building a device capable of factoring larger numbers is a major goal of quantum computing. Some small-scale demonstrations of an algorithm for quantum factoring (known as Shor's algorithm) exist, but these have used simplifications dependent on knowing the factors in advance. John Smolin et al . use a simple coin-tossing exercise to illustrate the dangers of over-simplification, and suggest a more stringent test for experimental demonstrations of Shor's algorithm. Shor’s quantum factoring algorithm exponentially outperforms known classical methods. Previous experimental implementations have used simplifications dependent on knowing the factors in advance. However, as we show here, all composite numbers admit simplification of the algorithm to a circuit equivalent to flipping coins. The difficulty of a particular experiment therefore depends on the level of simplification chosen, not the size of the number factored. Valid implementations should not make use of the answer sought.

• Publisher: Nature Publishing Group UK,Nature Publishing Group
• Subject: 639/705/117 / 639/766/483/481 / Algorithmics. Computability. Computer arithmetics / Algorithms / analysis / Applied sciences / Circuits / Classical and quantum physics: mechanics and fields / Coins / Computer science; control theory; systems / Equivalence / Exact sciences and technology / Experiments / Factors (Algebra) / Humanities and Social Sciences / multidisciplinary / Physics / Quantum computation / Quantum computing / Quantum information / Quantum theory / Science / Simplification / Theoretical computing