Proceedings PaperToward design principles for physically realizable algorithms for high-complexity computations
|Format||Member Price||Non-Member Price|
Implementation of the present form of the Shor factoring algorithm for numbers large enough to interest cryptographers and number theorists may pose problems of precision of measurement that apparently have received less attention than the problems of maintaining coherence during the algorithm's unitary transformations on its quantum registers. Hence, those whose primary interest is a major advancement of computational power may reasonably ask if other physical phenomena or other algorithm design principles might pose milder technical difficulties while providing desired computations. Recalling that Hopfield and Tank's neural network formula for solving the traveling salesman problem was originally inspired by the Hamiltonians of spin glasses has led to a possible spin-relaxation method for solving factorization problems. The search process starts at quasi-Monte Carlo points that in research on numerical integration have been shown to be adequate samples of unit hypercubes. Feasibility of implementation of this method has not been shown, with two evident types of difficulty: initializing a spin system to the quasi-Monte Carlo points, and achieving the needed wide dynamic range of couplings between spins. As real spin system both evolve unitarily under conditions where coupling to the rest of the world can be neglected and display relaxation behavior where coupling is significant, there may be a useful complementarily between unitary transformations and relaxation processes in implementing different phases of a computation, and alternating between them would provide some degree of noise suppression comparable to that found in conventional digital technology. The strategy of equipartitioning searches provides a possible framework for factoring some computations into feasible portions.