Enzo Michelangeli wrote:
[snip]
>1. Converting a generic codebreaking problem into an NP-complete one
>with a transformation of polynomial complexity, while probably
>possible, is not trivial at all.
In this case, solving the problem is actually easier than transforming
the problem into an NP-complete problem. The state of a quantum
computer is a unit 2^k dimensional vector, where k is the number of
qubits. The initial state is a diagonal equidistant from all the axes
whose components are all positive. Grover's algorithm first negates the
component corresponding to the correct answer, then rotates the vector
slightly, increasing the distance between the new state and the original
diagonal. This is repeated sqrt(2^k) = 2^(k/2) times.
The process has to be repeated so many times because distances between
quantum states are preserved in linear QM. All you've got to work with
are rotations & reflections of the state vector.
In nonlinear QM, however, distances aren't preserved, and you would only
have to apply the selection rule once. After that, you'd apply a
"stretching" algorithm that increases the distance between the diagonal
and the states near it. A process like this could distinguish between a
superposition of inputs that contains a solution and one that doesn't,
reducing the problem to a binary search.
[snip]
>2. As James D. noted, away from strong gravitational fields the
>equations of Quantum Mechanics, which are linear, appear extremely
>consistent with the measured reality.
Yep. "Extremely" meaning something like an inconceivable 14 decimal
places. It will be interesting to see if this paper provides a way
around the linearity or not.
[snip]
--
Mike Stay
Cryptographer / Programmer
AccessData Corp.
mailto:[EMAIL PROTECTED]
