continued . . . Why be interested in quantum conputing?
is an obvious one to ask. The answers to it are all variations of a single generic one. Problem P is currently intractable, i.e., tractable only in exponential time. The availability of a quantum computer would make itb tractable in exponential time. An example. Almost all modern encryption schemes are based on the intractability of the problem of factoring a large composite number. If, say, an arbitrary composite 2048-bit binary integer could be factored readily they would all be rendered useless. Enter Shor's algorithm, with a storm warning of jargon to come. His algorithm makes it possible to factror such an n-bit composite binary integer using 2n + 3 qubits in polynomial time on a quantum computer. This of course is the reason for the NSA's interest in quantum computing. The availability of a quantum computer would make all current cryptography transparent to anyone with access to such a machine. On 1/3/14, John Gilmore <[email protected]> wrote: > Since the last trime quantum computing was doiscussed here I have > received several requests for a reference to an elementary but > adequate introductory discussion of it. > > The best reference is the small book > > Williams, Colin P., and Scott H. Clearwater. Explorations in quantum > computing. New York: Springer-Verlag, 1994. > > It is certainly elementary in this context, but 'elementary' here does > not mean that it is at all accessible to potential readers who are > uncomfortable with complex numbers and the standard arithmetic > operations on them or 2) matrix algebra. It is not. > > The question > > Why be interested in q > > John Gilmore, Ashland, MA 01721 - USA ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to [email protected] with the message: INFO IBM-MAIN
