Abstracts List

This page contains the abstracts already submitted. Make sure you got the updated version by using the reload button. This list is not sorted, the abstracts appear ordered as they were submitted.

Quantum Counting

Authors:Gilles Brassard [ Universite de Montreal (LITQ),brassard@iro.umontreal.ca]
Alain Tapp [ Universite de Montreal (LITQ),tappa@iro.umontreal.ca ]

Abstract

Shor's algorithm for factorization and Grover's algorithm for table lookup are no doubt among the most important results in quantum algorithms. In this presentation, we will show how to use ideas coming from these two algorithms to perform a completely novel task. Suppose a function F is given as a black box, one can find an x for which F(x)=1 much more efficiently with Grover's algorithm than with any classical technique. Now suppose one wants to evaluate the size of {x|F(x)=1}, that is, to count the number of solutions to F. We will present an algorithm that can approximate this size with a selected accuracy.

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.

• If we take P=c N^(1/2) then |t'-t|< (2 Pi t^(1/2))/c + (Pi^2)/(c^2).
• For P=c(N/t)^(1/2) we have (1+Pi/c)^2 < t'/t < 1/(1+Pi/c)^2.
• Finally with P=c(t'N)^(1/2) we have t'=t with bounded probability.
Of course, the algorithm does not need any prior information about t. The number of evaluations of F needed to obtain the selected precision is quite lower than the best possible sampling algorithm. This technique is also more efficient than naive classical uses of Grover's algorithm.

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

• No paper version is available.

Conjugated Operators in Quantum Algorithms

Abstract

We address the question of understanding quantum algorithms in terms of unitary operators. Many quantum algorithms can be expressed as applications of operators formed by conjugating so-called classical operators. The operators that are used for conjugation are determined by the problem and any additional structure possessed by the Hilbert space that is acted upon. We prove many new commutative laws between these different operators, and we use those to phrase and analyze old and new problems and algorithms. As an example, we review the Abelian subgroup problem. We then introduce the problem of determining a group homomorphism, and we give classical and quantum algorithms for it. We also generalize Deutsch's problem and improve the previous best algorithms for earlier generalizations of it.

• A paper version is also available here

Quantum Computing and Counting Complexity

Authors:Lance Fortnow [ University of Chicago,fortnow@cs.uchicago.edu]

Abstract

Quantum computing has a large advantage over traditional probabilistic approaches because of "interference", the ability of "bad" computation paths to cancel each other leaving the "good" computation paths with a higher probability of occurrence. A similar phenomenon developed in the study of counting complexity several years ago. Counting complexity looks at not just whether a certain search problem has a solution, but rather at the number of solutions. Valiant first looked at these questions, developing the #P functions, which count the number of accepting paths of NP machines. A whole area of study quickly developed studying #P functions and many complexity classes based on these functions. In order to help understand the power of counting classes, Fenner, Fortnow and Kurtz developed the GapP functions, which are the class of #P functions closed under subtraction. One can view GapP functions as putting positive and negative weights on the computation paths of an NP machine. This yields a cancellation effect not unlike the one we see with quantum machines. Also, GapP has some wonderful closure properties that give us powerful tools for studying their behavior. In this survey talk, we will give a brief history and sampling of results about GapP functions. We then will present a surprisingly tight connection between GapP functions and Quantum Turing machines. We describe two recent results using this connection: - (Fortnow-Rogers) BQP sits in a previously studied complexity class AWPP. This result gives an easy proof that BQP is in PP and in fact shows that BQP is low for PP, i.e. PP with a BQP oracle is still PP. This also leads to new relativized results about BQP. - (Fenner-Green-Homer-Pruim) An exact characterization of NQP as the well-studied complexity class co-C=P.

• No paper version is available.

Classical Foundations of Oblivious Transfer

Authors:Christian Cachin [ MIT,http://theory.lcs.mit.edu/~cc]

Abstract

We show that oblivious transfer can be based on a very general notion of asymmetric information difference. We investigate a Universal Oblivious Transfer , denoted UOT(X,Y), that gives Bob the freedom to access Alice's input X in an arbitrary way as long as he does not obtain full information about X. We show that oblivious transfer can be reduced to a single execution of UOT(X,Y) with Bob's knowledge Y restricted in terms of min-entropy and Rényi entropy of order µ>1. For independently repeated UOT the reduction works even if only Bob's Shannon information is restricted, i.e. if H(X|Y)>0 in every UOT(X,Y).

This link leads to a paper version not located on our server.

• No paper version is available.

Quantum computation of Fourier transforms over symmetric groups

Authors:Robert Beals [ University of Arizona,beals@math.arizona.edu]

Abstract

Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups. That is, at some point in the computation, the machine is in a superposition of states corresponding to elements of a finite abelian group $G$, and in quantum polynomial time (i.e., polynomial in $\log|G|$), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of $G$. We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups $S_n$, adapting results obtained by Clausen and Diaconis--Rockmore to the quantum setting.

• A paper version is also available here

Computation of polynomial invariants of quantum states and quantum codes

Authors:Markus Grassl [ IAKS, University of Karlsruhe,grassl@ira.uka.de]
Thomas Beth [ IAKS, University of Karlsruhe,EISS_Office@ira.uka.de]
Martin Roetteler [ IAKS, University of Karlsruhe,roettele@ira.uka.de]

Abstract

Non-locality is one of the astonishing phenomena in quantum mechanics. Well-known examples are EPR pairs and the GHZ state. One common feature of these states is that the non-local properties do not change under local transformations, i. e., unitary operations acting independently on each of the subsystems. The error-correcting properties of quantum codes do not change under local transformations, too. Any function that is invariant under local transformations can be used to describe these non-local properties. We focus on polynomials that are invariant under local transformations. Our work extends the results of Eric Rains on polynomial invariants of quantum codes. Rains showed that for an N-qubit-system there is a correspondence between N-tuples of permutations of k letters and homogeneous invariants of degree k. We will present a construction for homogeneous invariants that is based on labeled binary trees. This reduces the upper bound for the running time to find all invariants of degree k from (k!)^N to (2^k)^N. We will present further conditions that allow a reduction of the number of permutations that need to be considered. This makes the computation of all invariants feasible at least for small degree and few qubits. For the smallest example, a two-qubit system, we computed the Molien series that encodes the number of linearly independent homogeneous invariants for each degree. Combining our algorithm with this series, we computed a system of 21 invariants for which we were able to show that it generates all invariants up to degree 23. We conjecture that all invariants can be generated by those invariants.

• No paper version is available.

Relationships between quantum and classical space-bounded complexity classes

Authors:John Watrous [ University of Wisconsin,watrous@cs.wisc.edu]

Abstract

In this talk, the relative power of quantum and classical (probabilistic) machines, when the limiting resource is space rather than time, will be discussed. In particular, quantum simulations of probabilistic machines and probabilistic simulations of quantum machines will be presented which imply the following relationships for any suitable (space constructible and not sub-logarithmic) space bound s: (1) Any PTM which runs in space s and which halts absolutely (i.e. for each input, there exists some finite number of steps after which the machine halts with certainty) can be simulated in space O(s) by a QTM. If the PTM has probability of error bounded away from 1/2, or has one-sided error, the same is true of the QTM. In the case of unbounded error, the quantum machine may be taken to halt absolutely, but for the bounded error and one-sided error cases the QTM will not necessarily halt absolutely. (2) Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or running time for the QTM are required, but it is assumed that all transition amplitudes of the QTM are rational. It follows that unbounded error, space O(s) bounded QTMs and PTMs (with rational transition amplitudes/probabilities) are equivalent in power, and that QTMs can be simulated deterministically with at most quadratic increase in space. Quantum analogues of nondeterministic space-bounded classes, where acceptance or rejection is determined by whether QTMs accept with nonzero or zero probability, will also be mentioned. A result analogous to a recent result of [Fenner, Green, Homer and Pruim] holds for these space-bounded classes: quantum-NSPACE(s) = co-C=SPACE(s).

• No paper version is available.

Multiparty Quantum Communication Complexity

Authors:Wim van Dam [ University of Oxford/CWI Amsterdam,wimvdam@mildred.physics.ox.ac.uk]
Alain Tapp [ Universite de Montreal,tappa@iro.umontreal.ca]

Abstract

Quantum entanglement cannot be used to simulate communication among remote parties, but it can reduce the communication needed for some problems. Let each out of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We show that, for a particular function F, if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. On the other hand, we also show that, if no entangled particles are provided, then the classical communication complexity of F is roughly klog2 k. In terms of the number of parties, this proves for the first time a communication complexity separation better than a constant number of bits.

• No paper version available on our server.

Quantum Bit Commitment from a Physical Assumption

Authors:Louis Salvail [ BRICS,salvail@brics.dk]

Abstract

Bit commitment is a basic and fundamental cryptographic tool allowing a sender to give a piece of evidence that she has a bit x in mind. The receiver does not learn the bit from the information he receives but can ask the sender to unveil it. A secure bit commitment scheme must be
• hidding:the receiver cannot learn the bit from the piece of evidence,
• binding:the sender has only one choice when she unveils.
A weaker but usefull bit commitment scheme is obtained by relaxing the binding condition. We say that such a scheme is d-binding if for any execution of the commiting phase there exists a bit w such that the revelation of w has probability of success less than d. Any d-binding commitment scheme, with d<1, is sufficient in order to build a secure quantum oublivious transfer protocol with no significant increase in communication complexity.

However, Mayers has shown that quantum mechanics does not allow secure bit commitment schemes under the only assumption that quantum mechanics is correct. This no-go theorem is also valid for d-binding commitment schemes. If the quantum states ensemble describing the commitment of x=0 is nearly the same as the one describing the commitment of x=1, thus the commitment is hidding, then both bits can be unveiled with no possibility of detection. Although the attack can always be carried out in principle, it requires to run a quantum computer storing large entanglements during the time between the committing and the revelation phases.

In this talk, we assume that one party, the sender, cannot deal with arbitrarily large quantum states. Namely, there exists a limit t* on the number of photons (or q-bits) that can be measured coherently (a measurement involving no more than t* of the received q-bits is called a t*-coherent measurement). We show that under this extra assumption secure quantum bit commitment is possible for quite large values of t*. In particular, we describe a d-binding quantum bit commitment scheme secure against any t*-coherent measurement provided t*< µN for µ>0 and N is the number photons transmitted during the committing phase. As a corollary, the scheme is 2-aN-binding against any t*-coherent measurement provided t* < µN1/2 for some µ>0.

• No paper version is available.

Quantum Entanglement Purification

Authors:Charles H. Bennett [ T.J. Watson Laboratories,bennetc@watson.ibm.com]
Gilles Brassard [ Universite de Montreal,brassard@iro.umontreal.ca]
Sandu Popescu [ Newton Institute,s.popescu@newton.cam.ac.uk]
Benjamin Schumacher [ Kenyon College,schumacb@kenyon.edu]
John A. Smolin [ T.J. Watson Laboratories,clsmolin@watson.ibm.com]
William K. Wootters [ Williams College,William.K.Wootters@williams.edu]

Abstract

Entanglement is perhaps the most non-classical aspect of quantum mechanics. It is the soul of quantum teleportation and without it no nontrivial quantum computation would be possible. However, sharing long-lived entanglement between two distant observers is technologically challenging because of the fragility of quantum information, both in transit and through time. I shall explain how it is possible for two observers to purify an initial supply of imperfect entanglement, possibly obtained through a noisy quantum channel, by means of local operations and the exchange of classical information. This technique can be used to assist in the faithful transmission of quantum information over an unreliable quantum channel, and it may also have applications in quantum cryptography.

• The paper appears in PRL, Vol. 76, no. 5, 29 January 1996,pp.722-725.

Complexity limitations on quantum computation

Authors:Lance Fortnow [ University of Chicago,fortnow@cs.uchicago.edu]
John Rogers [ DePaul University,rogers@cs.depaul.edu]

Abstract

We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum class BQP.
• BQP is low for PP, i.e., PP(BQP) = PP.
• There exists a relativized world where P=BQP and the polynomial-time hierarchy is infinite.
• There exists a relativized world where P=BQP but P \neq (UP intersect coUP) and one-way functions exist. This gives a relativized answer to an open question of Simon.

• A paper version is also available here

Quantum Communication Complexity

Authors:Harry Buhrman [ CWI, Amsterdam, The Netherlands,buhrman@cwi.nl]

Abstract

We present a simple and general simulation technique that transforms any black-box quantum algorithm ({\it \a la} Grover's database search algorithm) to a quantum communication protocol for a related problem, in a way that fully exploits the quantum parallelism. We construct novel quantum communication protocols that are built from nontrivial quantum algorithms via this simulation. These protocols, combined with (old and new) classical lower bounds, are shown to provide the first asymptotic separation results between the quantum and classical (probabilistic) two-party communication complexity models. In particular, we obtain a quadratic separation for the bounded-error models, and an exponential separation for the zero-error models. This is joint work with Avi Wigderson and Richard Cleve

• No paper version is available.

Quantum Computer Algorithms and Interferometry

Authors:Michele Mosca [ University of Oxford,mosca@maths.ox.ac.uk]

Abstract

We highlight the relationship between the Quantum Fourier Transform and phase estimation. We describe a general scheme for introducing or 'kicking back' phases (based on Kitaev's technique) and generating a prescribed interference pattern with arbitrary precision. We review (and improve) some of the existing quantum algorithms and show how they are related to quantum phase 'kick-back' and phase estimation . (This talk is based primarily on a joint paper with R. Cleve, A. Ekert, and C. Macchiavello, Quantum Algorithms Revisited, to appear in Proc. Roy. Soc. Lond. A, and also available at quant-ph/9708016.)

• No paper version is available.

Quantum Computation and Communication

Authors:Richard Cleve [ University of Calgary,cleve@cpsc.ucalgary.ca]

Abstract

We derive computational lower bounds for the PARITY and MAJORITY function in the black-box model which demonstrate that these problems cannot be solved significantly faster by quantum algorithms than by classical algorithms. In particular, the kind of quadratic speed-up achieved by Grover's quantum technique for the OR function is impossible to obtain for these functions (in the black-box model). The lower bounds are derived from lower bounds in communication complexity. We also describe black-box algorithms that compute bounded-depth predicates (i.e. those in the polynomial hierarchy, between OR and MAJORITY) with near quadratic speed-up. This talk is based on joint work with Avi Wigderson and Harry Buhrman, as well as with Wim van Dam and Alain Tapp.

• No paper version is available.

Quantum Robots and Quantum Computers

Authors:Paul Benioff [ Argonne National Lab, Argonne IL USA,pbenioff@anl.gov] (This talk has been canceled)

Abstract

Validation of a presumably universal theory, such as quantum mechanics, requires a quantum mechanical description of systems that carry out theoretical calculations and systems that carry out experiments. The description of quantum computers is under active development. No description of systems to carry out experiments has been given. A small step in this direction is taken here by giving a description of quantum robots as mobile systems with on board quantum computers that interact with different environments of quantum systems. Some properties of these systems are discussed. A specific model based on the literature descriptions of quantum Turing machines is presented.

• No paper version is available.

Simulating quantum operations with mixed environments

Authors:Isaac L. Chuang [ Los Alamos National Laboratory,ike@isl.stanford.edu]
David P. DiVincenzo [ IBM T.J.Watson Research Center,divince@watson.ibm.com]
John A. Smolin [ IBM T.J.Watson Research Center,smolin@watson.ibm.com]
Barbara M. Terhal [ University of Amsterdam,terhal@phys.uva.nl]

Abstract

We will analyze to what extent quantum operations can be simulated efficiently by using mixed state environments instead of pure states. We will present numerical counterexamples that indicate that operations on qubits cannot always be simulated with a mixed single qubit environment. For the class of generalized depolarizing channels we show how a qutrit environment does suffice.

• No paper version is available.

Noisy Quantum Computation- Solved Problems, Open Problems

Authors:Dorit Aharonov [ Hebrew University,doria@cs.huji.ac.il]

Abstract

Recently it was shown that if quantum devices are made more reliable than a certain threshold, fault tolerant quantum computation is theoretically possible. (Aharonov and Ben-or, Knill Lafflamme and Zurek, Kitaev) I will survey the sequence of ideas which lead to this conclusion.

• No paper version is available.

On Noncommutative Hidden Subgroups

Authors:Mark Ettinger [ Los Alamos National Laboratory,ettinger@lanl.gov]

Abstract

To date perhaps the most illuminating formulation of known quantum algorithms is the Abelian Hidden Subgroup Problem. This framework includes both Simon's and Shor's results and casts these algorithms in a group-theoretic framework which both reveals the fundamental role of the Fourier transorm and indicates new research directions. Indeed a most natural question is if the hidden subgroups of noncommutative groups may be found efficiently by quantum computers. This question is all the more urgent given the fact that graph isomorphism reduces to it and Beals has already supplied the appropriate quantum fourier transform over the symmetric group. However harmonic analysis is more complex in the noncommutative case which makes this a challenging research problem. We will investigate the noncommutative hidden subgroup problem. We will review the general duality results known as Tannaka-Krejn duality, illustrate the necessity of new techniques by showing the limitations of the commutative methods in the case of several semidirect products, and provide evidence that the noncommutative hidden subgroup problem is solvable for Gelfand Pairs.

• No paper version is available.

Quantum attacks on classical bit commitment schemes

Authors:Gilles Brassard [ Université de Montréal,brassard@iro.umontreal.ca]
Claude Crépeau [ Université de Montréal,crepeau@iro.umontreal.ca]
Dominic Mayers [ Princeton University,mayers@cs.princeton.edu]
Louis Salvail [ BRICS,salvail@daimi.aau.dk]

Abstract

Protocols devised in the classical scenario are generally believed to retain their security properties when considered in the context of quantum computers. We show this belief is wrong. We demonstrate that some computational bit commitment schemes proven secure in the classical scenario are really useless in the quantum scenario. More precisely, we show that bit commitment schemes that are unconditionally concealing such as the computationally binding protocol due to Naor,Ostrovsky,Venkatasen,Yung or the two-prover protocol of Ben-Or,Goldwasser,Kilian,Wigderson can be cheated efficiently with a quantum computer, when these schemes are used to commit to the outcome of a quantum measurement. We use these results to defeat attempts to implement unconditional quantum bit commitment by bootstrapping with such schemes.

• No paper version is available.

How much information can one touch in k qbits ?

Authors:Amnon Ta-Shma [ ICSI,amnon@icsi.berkeley.edu]
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.