Progress review

During the last year, our research effort has been centered on four main avenues: (A) analysis of quantum coding and quantum inseparability by use of an information-theoretic approach previously developed by us; (B) study of quantum copying machines and derivation of no-cloning uncertainty relations; (C) investigation of the optical simulation of quantum networks; and (D) development of an improved quantum search algorithm based on nesting.  The report hereunder is organized by themes.

(A) Information-theoretic approach to quantum coding and inseparability 

We have investigated several applications of the unified framework for quantum information that we had developed in our earlier work (see QUIC report, June 97).  First, we have considered the calculation of entropic bounds on the achievable rate of reliable transmission of quantum information through a noisy quantum channel.  In analogy with its classical counterpart, a noisy quantum channel can be characterized by its loss, a quantity that depends on the channel input and the quantum operation performed by the channel.  The loss reflects the transmission quality: if the loss is zero, quantum information can be perfectly transmitted at a rate measured by the quantum source entropy.  By using block coding based on sequences of n entangled symbols, the average loss (defined as the overall loss of the joint n-symbol channel divided by n, when n tends to infinity) can be made lower than the loss for a single use of the channel.  In this context, we have examined several upper bounds on the rate at which quantum information can be transmitted reliably via a noisy channel, that is, with an asymptotically vanishing average loss while the one-symbol loss of the channel is non-zero.  These bounds on the channel capacity rely on the entropic Singleton bound on quantum error-correcting codes that we had derived in earlier work.  For the quantum erasure channel, our bound coincides with the exact capacity that was recently found by Bennett and coworkers.  We have also analyzed the entropic Singleton bound when the noisy quantum channel is supplemented with a classical auxiliary channel, and we concluded that a classical channel cannot be used to increase the Singleton bound.  This work is reported in paper [2].
Secondly, we have analyzed quantum inseparability using this information-theoretic approach.  The graduate student R. M. Gingrich participated in this work.  We have investigated the properties of the conditional amplitude operator, the quantum analog of the conditional probability (see paper [3]).  We showed that the spectrum of the conditional operator characterizing a quantum bipartite system is invariant under local unitaxy transformations and reflects its inseparability.  Furthermore, we proved that the conditional amplitude operator of a separable state cannot have an eigenvalue exceeding 1, which results in a necessary condition for separability.  We then derived a related "reductive" separability criterion, based on the positive map p -+ (Trp) - p. Any separable state is mapped by the tensor product of this map and the identity into a nonnegative operator, which provides a simple necessary condition for separability (see paper [4)).  This map reduces to time-reversal in the special case of two qubits, so that the reduction separability condition is then equivalent to partial transposition.  A simple connection between this map and complex conjugation
in the "magic" basis was also displayed.
Finally, we have investigated the duality between the concepts of "physical reality" and quantum reality in terms of quantum information theory.  We have shown that this formalism suggests a solution to quantum paradoxes such as the Einstein-Podolsky-Rosen and the Schroedinger-cat paradoxes (see paper [71).
 

(B) Quantum copying machines and no-cloning uncertainty relations 

First, we have discussed an information-theoretic approach to quantum copying, relying on the notion of quantum loss, a quantity that reflects the transmission quality in a noisy quantum channel.  More specifically, an entropic no-cloning inequality has been derived for a Hilbert space of arbitrary dimension, which describes the tradeoff between the losses of the channels leading to the two copies: LA + LB > 2S, where LA and LB are the losses characterizing outputs A and B of the cloner, respectively, while S is the source entropy.  This work is reported in paper [6].
Then, we have introduced a family of asymmetric Pauli cloning machines (PCM), which produces two distinct (approximate) copies of a single quantum bit, each emerging from a Pauli channel.  This is in contrast with the cloning machines considered in the literature, which are symmetric (both outputs being characterized by the same density operator).  The family of PCMs relies on a parametrization of 4-qubit wave functions for which all qubit pairs are in a mixture of Bell states, and is a natural generalization of the universal quantum copying machine introduced by Buzek and Hillery.  Using a particular class of asymmetric PCMs whose outputs emerge from (distinct) depolarizing channels, we have derived a no-cloning uncertainty relation governing the tradeoff between the quality of the copies of a quantum bit: a2 + ab + bl > 1, where a2 and b2 are the depolarizing fractions of the channels associated with outputs A and B, respectively.  It is, by construction, a tight inequality which is saturated using our PCM.  Finally, the subclass of symmetric PCMs has been used in order to express an upper bound on the quantum capacity of the Pauli channel, extending the bound that was previously known for the depolarizing channel.  In particular, the capacity of the Pauli channel of probabilities p. = x2, py @ y 2 and p, = z2, was shown to vanish if (x, y, z) lies outside an ellipsoid whose pole coincides with the depolarizing channel underlying the UCM.  This implies an upper bound on the capacity C of any Pauli channel associated with a point (x, y, z) located inside the ellipsoid, namely C < 1 - 2(X2 +y2 +Z2 +Xy +XZ +yZ).
This work is reported in paper 151.
In paper [9], we have considered the cloning of quantum states in a Hilbert space of arbitrary dimension.  We have generalized the Pauli cloning machines and introduced an (asymmetric) N-dimensional cloning machine.  We then showed that the complementarity between the two copies produced by a Pauli cloning machine and its N-dimensional extension results from an genuine uncertainty principle, much like that associated with Fourier transforms.  This uncertainty principle simply relates the probability distributions underlying the channels leading to the two outputs of the cloner.  Finally, we have analyzed the semi-classical limit of an infinite-dimensional cloning machine.

(C) Optical simulation of quantum networks

This research has been performed in collaboration with Paul G. Kwiat (Los Alamos National Laboratory), and is reported in papers [1,81.  We have suggested a constructive method for simulating small-scale quantum circuits using optical setups composed of linear optical devices.  It relies on the representation of several quantum bits by a single photon, and on the implementation of universal quantum gates using simple optical components such as beam splitters, phase shifters, etc.  This avoids the recourse to non-lineax Kerr media to effect quantum conditional dynamics, a severe constraint in the usual optical realization of quantum circuits.  A drawback of this technique is clearly the exponential increase of the resources (optical devices) with the size of the circuit.  Nevertheless, as optical components that simulate 1- and 2-bit universal quantum gates can be cascaded straightforwardly, a non-trivial quantum computing optical device can be constructed if the number of component qubits is not too large.  As an illustration, we have presented the optical analogue of the Brassard et al.'s 3-bit circuit for quantum teleportation.  This suggests that the optical realization of small quantum networks with present-day quantum optics technology is a reasonable goal, and that such a technique could be useful for demonstrating basic concepts of simple quantum algorithms or error-correction schemes.

(D) Nested quantum search

We have initiated a collaboration with Colin P. Williams (JPL) and Lov K. Grover (Lucent) which concerns the development of improved quantum algorithms for NP-complete problems.  We have shown that a quantum algorithm can be devised that exploits the structure of a tree search problem by nesting the standard (unstructured) quantum search algorithm.  The latter is used to construct a seaxch operator which, itself, is nested within another search algorithm at an upper nesting level.  The expected number of iterations required to find the solution of an average instance of a constraint satisfaction problem is estimated to scale as Vdc', where d is the dimension of the search space and a < 1 is a scaling coefficient that depends on the nesting depth and the problem considered.  When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, this constant a is estimated to be around 0.62 for average instances of maximum difficulty.  This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart.  Nevertheless, it is an exponential speedup with respect to the time needed to solve the problem by use of the standard unstructured quantum search algorithm, which scales as %Fd.  We believe that this technique is applicable in many structured search problems.  This work is reported in paper [10].

Participating personnel:

* Steve E. Koonin, Co-PI

* Chris Adami, Senior Research Fellow

* Nicolas J. Cerf, Senior Research Fellow (also Visiting Scientist at JPL)

* Robert M. Gingrich, Graduate Student
 

List of papers published or submitted

1. Optical simulation of quantum logic, N. J. Cerf, C. Adami, and P. G. Kwiat, Phys.  Rev.  A 57 (1998), R1477-Rl480.

2. Entropic bounds on coding for noisy quantum channels, N. J. Cerf, Phys.  Rev.  A 57 (1998), 3330-3347.

3. Quantum extension of conditional probability, N. J. Cerf and C. Adwni, submitted to Phys.  Rev.  A. (quant-ph/9710001)

4. Reduction criterion for separability, N. J. Cerf, C. Adami, and R. M. Gingrich, submitted to Phys.  Rev.  A. (quant-ph/9710001)

5. Quantum cloning and the capacity of the Pauli channel, N. J. Cerf, submitted to Phys.  Rev.  Lett. (quant-ph/9803058)

6. Infor-rnation-theoretic aspects of quantum copying, N. J. Cerf, Lecture Notes in Computer Science, (Springer-Verlag, 1998), in press.  Special issue for lst NASA Workshop on Quantum Computation and Quantum Communication QCQC'98.

7. What information theory can tell us about quantum reality, C. Adami and
N. J. Cerf, Lecture Notes in Computer Science, (Springer-Verlag, 1998), in press.  Special issue for lst NASA Workshop on Quantum Computation and Quantum Communication QCQC'98. (quant-ph/9806047)

8. Quantum computation with linear optics, C. Adami and N. J. Cerf, Lecture Notes in Computer Science, (Springer-Verlag, 1998), in press.  Special issue for Ist NASA Workshop on Quantum Computation and Quantum Communication QCQC'98. (quant-ph/9806048)

9. Asymmetric quantum cloning machines, N. J. Cerf, Acta Physica Slovaca 48 (1998), in press.  Special issue on Quantum Optics and 'Quantum Information. (quant-ph/9805024)

10. Nested quantum search and NP-cornplete problems, N. J. Cerf, L. K. Grover and C. P. Williams, Applicable Algebra in Engineering, Communication and Computing (Springer-Verlag, 1998).  Special issue for the Dagstuhl Seminar on Quantum Algorithms. (quant-ph/9806078)

List of presentations

1. Singleton bounds for quantum codes and channels, N. J. Cerf Contributed talk, 5th Quantum Computation Workshop, Institute for Scientific Interchange Foundation, Torino, Italy, July 1997.

2. An introduction to quantum information theory, N. J. Cerf Invited seminar, Center for Nonlinear Phenomena and Complex Systems, Brussels University, Belgium, 12 November 1997.

3. What information theory can tell us about quantum reality, C. Adami, Contributed talk, lst NASA International Conference on Quantum Computing and Quantum Communications QCQC '98, Palm Springs, 17-20 February 1998.

4. Quantum computation with linear optics, C. Adami, Contributed talk, Ist NASA International Conference on Quantum Computing and Quantum Communications QCQC '98, Palm Springs, 17-20 February 1998.

5. Information-theoretic aspects of quantum copying, N. J. Cerf, Contributed talk, lst NASA International Conference on Quantum Computing and Quantum Communications QCQC '98, Palm Springs, 17-20 February 1998.

6. Pauli cloning machines and their many-dimensional generalization, N. J. Cerf, Invited talk, Dagstuhl Seminar on Quantum Algorithms, Wadern, Germany, 10-15 May 1998.

7. Nested quantum search, N. J. Cerf, Invited talk, Dagstuhl Seminar on Quantum Algorithms, Wadern, Germany, 10-15 May 1998.