Toward design principles for physically realizable algorithms for high-complexity computations

William David Miller

doi:10.1117/12.312637

6 July 1998 Toward design principles for physically realizable algorithms for high-complexity computations

William David Miller

Proceedings Volume 3385, Photonic Quantum Computing II; (1998) https://doi.org/10.1117/12.312637
Event: Aerospace/Defense Sensing and Controls, 1998, Orlando, FL, United States

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.

Citation Download Citation

William David Miller "Toward design principles for physically realizable algorithms for high-complexity computations", Proc. SPIE 3385, Photonic Quantum Computing II, (6 July 1998); https://doi.org/10.1117/12.312637

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
10 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Quantum computing

Computing systems

Numerical integration

Quantum communications

Binary data

Superposition

Neural networks

Show All Keywords

Keywords/Phrases

Search In:

Publication Years