Umesh Vazirani [ Berkeley,vazirani@cs.berkeley.edu]
Abstract
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").
No paper version is available.
Quantum key distribution is unconditionally secure.
Authors:Dominic Mayers [ Princeton,mayers@cs.princeton.edu]
Andrew Yao [ Princeton,yao@cs.princeton.edu]
Abstract
We explain the basic technique used to prove the unconditional security of quantum cryprography.
Unconditional security means a security against all attacks. There has been several claims of
security in the past. The presented work is different because it is the only one that carefully
considers all attacks. The essential of the proof was first published by Mayers in Crypto96. It
was based on techniques and basic concepts provided by Yao in STOC95 and Mayers Crypto95.
No paper version is available.
Quantum Effects in Algorithms
Authors:Richard Jozsa [ University of Plymouth,rjozsa@plymouth.ac.uk]
Abstract
There are several well known quantum algorithms which represent a substantial speedup over
any known classical algorithm for the corresponding problem. This leads to the question of
understanding precisely what the essential quantum physical effect is, that gives rise to
this computational facility and why it cannot occur within classical physics.
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.
Almost any quantum mechanical system can
perform rapid search
Authors:Lov K. Grover [ Lucent,lkg@mhcnet.lucent.com]
Abstract
A quantum computer has a clear advantage over a classical computer for exhaustive search.
The quantum mechanical algorithm for exhaustive search was originally derived by using
subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard
(W-H) transform. This paper shows that this algorithm can be implemented by replacing the
W-H transform by almost any quantum mechanical operation. This leads to several new
applications where it improves the number of steps by a square-root. It also broadens the
scope for implementation since it demonstrates quantum mechanical algorithms that can
readily adapt to available technology.
The paper appears in quant-phys/9712011.
Alice, Bob and Eve in Quantumland
Authors:Tal Mor [ Université de Montréal (LITQ),mor@iro.umontreal.ca]
Abstract
Security of quantum key distribution against sophisticated attacks
is among the most important issues in quantum information theory.
We prove security against a very important class of attacks
called collective attacks which use quantum memories and
gates, and which are directed against the final key.
Although attacks stronger than the collective attacks can exist
in principle, no explicit example was found and it is conjectured that
security against collective attacks implies also security against any
attack.
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).
No paper version is available from our server.
Quantum Channel Capacities
Authors:John Smolin [ T.J. Watson Laboratories,clsmolin@watson.ibm.com]
Abstract
The existence of coding schemes to allow unknown
quantum states to be faithfully transmitted through
a noisy channel despite the impossibility of
cloning goes counter to our intuition. We explain
the different kinds of quantum capacities and how
it is that they can arise, using the quantum
analog of the classical erasure channel as a framework.
Using a new result that nonunitary encodings are not
necessary, for the quantum erasure channel all the capacities can be
derived exactly. We compare these to
those of the depolarizing channel, for which only upper
and lower bounds on the capacities are known.
See:
H. Barnum, J.A. Smolin, B.M. Terhal, Results on Quantum Channel
Capacity, quant-ph/9711032(1997).
Charles H. Bennett, David P. DiVincenzo, John A.
Smolin, William K. Wootters,
Mixed State Entanglement and Quantum Error Correction,
Phys. Rev. A 54, 3824 (1996), also in quant-ph/9604024.
Charles H. Bennett, David P. DiVincenzo, John A. Smolin,
Capacities of Quantum Erasure Channels,
Phys. Rev. Letts. 78, 3217 (1997), also in quant-ph/9701015.
No paper version is available from our server.
Quantum and Classical Information: Interactions and Reductions
Authors:Charles H. Bennett [ T.J. Watson Laboratories,bennetc@watson.ibm.com]
Abstract
I will survey the interaction between entanglement and classical
information, and the reducibilities among quantum states of
multi-partite systems in the presence of classical communication.
Recent relevant eprints include quant-ph/9701015
and quant-ph/9604024.
No paper version is available from our server.
Quantum Lower Bounds by Polynomials
Authors:Robert Beals [ University of Arizona,beals@math.arizona.edu]
Harry Buhrman [ CWI,buhrman@cwi.nl]
Richard Cleve [ University of Calgary,cleve@cpsc.ucalgary.ca]
Michele Mosca [ University of Oxford,mosca@maths.ox.ac.uk]
Ronald de Wolf [ CWI,rdewolf@cwi.nl]
Abstract
We examine the number T of oracle calls that a quantum network requires
to compute some Boolean function on {0,1}N. We assume the so-called
blackbox model, where the input is given as an oracle,
and consider exact error-free computation as well as computation
with bounded error-probability.
We show that the acceptance probability of a network with T oracle calls
can be written as an N-variate polynomial of the input, having degree
at most 2T (this result is also implicit in earlier work by Lance Fortnow).
Using lower bounds on the degrees of polynomials that equal or approximate
Boolean functions, we derive lower bounds on T.
In particular:
- To compute the parity function on a quantum network, T=N/2 is
both necessary and sufficient. This holds for exact as well as for
bounded-error computation.
-
To compute the or and and functions exactly,
we need T=N.
Hence exact database search also requires N oracle calls, whereas Grover's
algorithm requires only O(N1/2) queries for bounded-error search.
Our method allows us to give a new proof of the well known
\Omega(N1/2) lower bound on bounded-error search.
If we restrict to inputs that satisfy some promise, then quantum networks
can sometimes achieve an exponential speed-up compared to classical
randomized methods (Deutsch-Jozsa, Simon).
However, we prove that without promises quantum computing can achieve
only a limited speed-up in the blackbox model:
If a quantum network can compute some total Boolean function F
using T oracle calls with bounded error, then a classical deterministic
decision tree can compute F exactly in O(T6) oracle calls.
No paper version is available.
