On a method of solving SAT efficiently using the quantum Turing machine
説明
In this paper, under an assumption that superposed physical states can be observed without collapsing the superposition, we show that the satisfiability problem (SAT, for short) can be solved by a quantum Turing machine in O(2/sup n/4/) time. This assumption is not widely accepted among physicists, however, (Aharonov et al., 1993) conjecture that a physical state actually exists as a superposition and can be observed without collapsing the superposition. >
収録刊行物
-
- Proceedings Workshop on Physics and Computation. PhysComp '94
-
Proceedings Workshop on Physics and Computation. PhysComp '94 177-185, 2002-12-17
IEEE Comput. Soc. Press