6 July 1998 Toward design principles for physically realizable algorithms for high-complexity computations
Author Affiliations +
Abstract
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.
© (1998) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
William David Miller, William David Miller, } "Toward design principles for physically realizable algorithms for high-complexity computations", Proc. SPIE 3385, Photonic Quantum Computing II, (6 July 1998); doi: 10.1117/12.312637; https://doi.org/10.1117/12.312637
PROCEEDINGS
10 PAGES


SHARE
RELATED CONTENT

Probabilistic logic of quantum computers
Proceedings of SPIE (November 10 1996)
GFSOP-based ternary quantum logic synthesis
Proceedings of SPIE (September 07 2010)
Quantum algorithms
Proceedings of SPIE (July 31 2002)
Vibrational decoherence in ion-trap quantum computers
Proceedings of SPIE (July 05 1998)
Is quantum parallelism real?
Proceedings of SPIE (April 02 2008)

Back to Top