Let P be the number of calls to the function F, N the size of the domain of F, t the size of {x|F(x)=1} and t' our estimate of t. For selected values of P, which is a good indicator of the time avalaible for computation, we have the following results.
The basic ideas regarding the algorithm we will present have been exposed in section 5 of [1]. The final version is in progress.
This work has been done in collaboration with Gilles Brasard and Peter Hoyer at the "Laboratoire d'Informatique Theorique et Quantique" of "L'Universite de Montreal".
[1] Michel Boyer, Gilles Brassard, Peter Hoyer, and Alain Tapp.
"Tight bounds on quantum searching",
In Proceedings of the Fourth Workshop on Physics of Computation, pages 36--43, 1996.
quant-ph/9605034
This link leads to a paper version not located on
our server.
Holevo's theorem states that k qbits can transmit at most k classical bits of information. Yet, it does not rule out the possibility that only one bit of information is obtained, BUT OF OUR CHOICE. Thus we ask is it possible that one can encode n classical bits x_1...x_n into k qbits, with k much smaller than n, s.t. for any 1 \le i \le n, there is a measurement that for any encoded word v=v(x) recovers the i'th bit of x, x_i, with success probability at least delta=1/2+epsilon (\epsilon > 0). We call such a scheme an n->k encoding with success probability delta (and epsilon advantage).
A simple example shows that a 2->1 encoding with success probability of 0.86.. exists, while no 2->1 probabilistic encoding can achieve any positive advantage. In fact, even a 3->1 encoding with 0.79 success probability exists. This naturally raises the question of the asymptotic behavior of such encodings.
A simple information theoretic argument shows that any n->m probabilistic encoding with success probability delta requires m to be at least (1-H(delta))n, where H is the Shannon entropy function. Thus, in the probabilistic model, if we want constant advantage, m must be a constant fraction of n. The information theoretic argument, as it is, does not extend to the quantum model where a bit is learnt by a measurement, and a measurement causes unrecoverable destruction to the given code-word. Yet, we present a proof that even in the quantum world, there is no way to encode n -> n/clog(n) with a constant advantage. Our proof also covers a quantum encoder that given an input x, has a probability distribution over k-qbit code-words.
One notable variant of the problem which is not covered
by our proof, is the variant where we replace the requirement
"for any v=v(x) and for any 1 \le i \le n" with the weaker requirement
"for any v=v(x), for MOST 1 \le i \le n".
We do not know yet whether this is a technical detail,
to be fixed by a better proof,
or not.
We point out that this might have implications to a new class we define, which
we call QNP (for "QUANTUM NP").
We give an analysis of the fast fourier transform algorithm as implemented in the quantum context and relate its exponential speedup to specific properties of quantum entanglement (which have been summarised in [1]). These properties appear to underlie all of the known quantum algorithms and apply to FFT algorithms over general abelian groups.
The above properties of entanglement do not exhaust all the ways in which quantum physics differs from classical physics. We consider the question of whether there are other different quantum effects which may be exploited for novel computational possibilities. We describe the example of ``counterfactual quantum computation'' -- a quantum mechanical method of learning the result of a computation without running the computer. It is based on properties of quantum measurement and relates to some vexing interpretational issues.
[1] R. Jozsa (1997) ``Entanglement and Quantum Computation'' available at
quant-phys/9797934.
The paper appears in quant-phys/9712011.
As a special case of the collective attacks, our work also proves security against the much simpler individual-particle attacks.
Previous related works:
C. H. Bennett, T. Mor, and J. A. Smolin, Phys. Rev. A
54 , 2675 (1996).
E. Biham and T. Mor, Phys. Rev. Lett. 78 , 2256
(1997).
E. Biham and T. Mor, Phys. Rev. Lett. 79, 4034
(1997).