Computer Science – Computational Complexity
Scientific paper
2006-10-19
Computer Science
Computational Complexity
Final version, 34 pages. Theorem 3 generalized and strengthened. Review results implemented. Typos corrected
Scientific paper
Voltage peaks on a conventional computer's power lines allow for the well-known dangerous DPA attacks. We show that measurement of a quantum computer's transient state during a computational step reveals information about a complete computation of arbitrary length, which can be extracted by repeated probing, if the computer is suitably programmed. Instant computing, as we name this mode of operation, recognizes for any total or partial recursive function arguments lying in the domain of definition and yields their function value with arbitrary small error probability in probabilistic linear time. This implies recognition of (not necessarily recursively enumerable) complements of recursively enumerable sets and the solution of the halting problem. Future quantum computers are shown to be likely to allow for instant computing, and some consequences are pointed out.
No associations
LandOfFree
Instant Computing - A New Computation Paradigm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Instant Computing - A New Computation Paradigm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instant Computing - A New Computation Paradigm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-12615