X-Message-Number: 7280
Date: 08 Dec 96 11:33:12 EST
From: yvan Bozzonetti <>
Subject: Abstracts with comments on quantum computers


Quantum computers open the possibility of a "quantum jump" in computing power of

near 26 orders: There where a classical computer can do one operation, a quantum
one can make 100 million of billion of billion operations... The interest in
cryonics are in computing correction worked out by nanomachines, mapping at

molecular level a full body before repair and brain or full body simulations for
up loading if there is no nanotech solution.

Los Alamos National Laboratory has a public archive for many domain of hard
science, quantum physics is one of them. The following abstracts come from the
quant-ph archive for November 1996. You can get abstracts for other months by

sending an e-mail to:  with, for example, the subject line:

list 9610.abs 9606.abs

and nothing in the message body. That particular order will bring you abstracts
of the October and June archive. to get a full text, use the order in the
subject line:

get 9611001  (to get the first paper of the November 96 month).

To read full papers you'll need to decompress them using uudecode, untar,
undoing gz and a TeX reader. I put my short personal comments between stars:
***my-comments***

\\
Paper: quant-ph/9611001
From: 
Date: Fri, 1 Nov 96 11:30 EST

Title: Quantum shadow enumerators
Authors: E. M. Rains (AT&T Research)
Comments: AMSTeX, 10 pages, no figures, submitted to IEEE Trans. Inf. Theory
\\
  In a recent paper [quant-ph/9610040], Shor and Laflamme define two ``weight
enumerators'' for quantum error correcting codes, connected by a MacWilliams
transform, and use them to give a linear-programming bound for quantum codes.
We extend their work by introducing another enumerator, based on the classical
theory of shadow codes, that tightens their bounds significantly. In
particular, nearly all of the codes known to be optimal among additive quantum
codes (codes derived from orthogonal geometry ([quant-ph/9608006])) can be
shown to be optimal among all quantum codes. We also use the shadow machinery
to extend a bound on self-dual additive codes (E. Rains, N. Sloane, manuscript
in preparation) to general codes, obtaining as a consequence that any pure code
of length n can correct at most floor((n+1)/6) errors.
\\

********* correcting errors is the main problem in practical Q-computers********
\\
Paper: quant-ph/9611004
From: Tad Hogg <>
Date: Mon, 4 Nov 1996 11:55:24 MST

Title: A Framework for Quantum Search Heuristics
Authors: Tad Hogg
Comments: 8 pages, Latex, 5 figures, to appear at PhysComp96, further
  information available at ftp://parcftp.xerox.com/pub/dynamics/quantum.html
\\
  A quantum algorithm for combinatorial search is presented that provides a
simple framework for utilizing search heuristics. The algorithm is evaluated in
a new case that is an unstructured version of the graph coloring problem. It
performs significantly better than the direct use of quantum parallelism, on
average, in cases corresponding to previously identified phase transitions in
search difficulty. The conditions underlying this improvement are described.
Much of the algorithm is independent of particular problem instances, making it
suitable for implementation as a special purpose device.
\\
***No more than 2 yrs agos, many predicted there could be nothing useful done
with a QC because no software could be implemented on them*****


\\
Paper: quant-ph/9611006
From: "Christopher A. Fuchs" <>
Date: Mon, 4 Nov 1996 20:24:00 -0800 (PST)

Title: Entanglement-Enhanced Classical Communication on a Noisy Quantum Channel
Authors: Charles H. Bennett, Christopher A. Fuchs, and John A. Smolin
Comments: 10 pages, LaTeX, to appear in Proceedings of the 3rd International
  Workshop on Quantum Communication and Measurement; See also
  http://vesta.physics.ucla.edu/~smolin/
\\
  We consider the problem of trying to send a single classical bit through a
noisy quantum channel when two transmissions through the channel are available
as a resource. Classically, two transmissions add nothing to the receiver's
capability of inferring the bit. In the quantum world, however, one has the
possible further advantage of entangling the two transmissions. We demonstrate
that, for certain noisy channels, such entangled transmissions enhance the
receiver's capability of a correct inference.
\\
***sending uncorrupted messages between different parts of a QC is of utmost
practical interest****

\\
Paper: quant-ph/9611013
From: Juan Fernando Poyatos <>
Date: Sun, 10 Nov 1996 11:56:29 +0100

Title: Complete Characterization of a Quantum Process: the Two-Bit Quantum Gate
Author: J. F. Poyatos, J. I. Cirac (Departamento de Fisica Aplicada,
  Universidad de Castilla--La Mancha, Ciudad Real, Spain), P. Zoller
  (Institut fuer Theoretische Physik, Universitaet Innsbruck, Austria)
Comments: Accepted for publication in Physical Review Letters 08Nov96
  (submitted 15Jly96)
\\
  We show how to fully characterize a quantum process in an open quantum
system. We particularize the procedure to the case of a universal two-qubit
gate in a quantum computer. We illustrate the method with a numerical
simulation of a quantum gate in the ion trap quantum computer.
\\


\\
Paper: quant-ph/9611021
From: Tad Hogg <>
Date: Wed, 13 Nov 1996 12:48:12 MST

Title: Quantum Smart Matter
Authors: Tad Hogg and J. Geoffrey Chase

Comments: 15 pages, Latex, 3 figures, this is an extended version of a paper to
  appear at PhysComp96, further info available at
  ftp://parcftp.xerox.com/pub/dynamics/quantum.html
\\
  The development of small-scale sensors and actuators enables the construction
of smart matter in which physical properties of materials are controlled in a
distributed manner. In this paper, we describe how quantum computers could
provide an additional capability, programmable control over some quantum
behaviors of such materials. This emphasizes the need for spatial coherence, in
contrast to the more commonly discussed issue of temporal coherence for quantum
computing. We also discuss some possible applications and engineering issues
involved in exploiting this possibility.
\\
***An idea with far reaching consequences than even nanotechnology, may be the
idea of the year****

\\
Paper: quant-ph/9611025
From: Dorit Aharonov <>
Date: Thu, 14 Nov 1996 13:44:10 +0200 (IST)
Date (revised): Fri, 15 Nov 1996 12:57:42 +0200 (IST)

Title: Fault Tolerant Quantum Computation with Constant Error
Authors: Dorit Aharonov (Physics and computer science, Hebrew Univ.) and
  Michael Ben-Or (Computer science, Hebrew univ.)
Comments: 18 pages, now includes bibliography
\\
  Recently Shor showed how to perform fault tolerant quantum computation when
the error probability is logarithmically small. We improve this bound and
describe fault tolerant quantum computation when the error probability is
smaller than some constant threshold. The cost is polylogarithmic in time and
space, and no measurements are used during the quantum computation. The result
holds also for quantum circuits which operate on nearest neighbors only. To
achieve this noise resistance, we use concatenated quantum error correcting
codes. The scheme presented is general, and works with all quantum codes that
satisfy some restrictions, namely that the code is ``proper''.
  We present two explicit classes of proper quantum codes. The first example of
proper quantum codes generalizes classical secret sharing with polynomials. The
second uses a known class of quantum codes and converts it to a proper code.
This class is defined over a field with p elements, so the elementary quantum
particle is not a qubit but a ``qupit''. With our codes, the threshold is about
10^(-6). Hopefully, this paper motivates a search for proper quantum codes with
higher thresholds, at which point quantum computation becomes practical.
\\

*** When errors can't be corrected it's nice to have a system able to cope with
then*****

\\
Paper: quant-ph/9611027
From:  (Andrew Steane)
Date: Sat, 16 Nov 1996 14:49:19 +0000

Title: Active stabilisation, quantum computation and quantum state synthesis
Authors: Andrew Steane (Clarendon Laboratory, Oxford University)
Comments: 8 pages LaTeX plus 4 figures. Submitted to Phys. Rev. Lett
\\
  Active stabilisation of a quantum system is the active suppression of noise
(such as decoherence) in the system, without disrupting its unitary evolution.
Quantum error correction suggests the possibility of achieving this, but only
if the recovery network can suppress more noise than it introduces. A general
method of constructing such networks is proposed, which gives a substantial
improvement over previous fault tolerant designs. The construction permits
quantum error correction to be understood as essentially quantum state
synthesis. An approximate analysis implies that algorithms involving very many
computational steps on a quantum computer can thus be made possible.
\\

*****The last phrase must be remembered when critics say QC can't do anyting of
practical value****

\\
Paper: quant-ph/9611028
From: Dorit Aharonov <>
Date: Sun, 17 Nov 1996 18:40:20 +0200 (IST)

Title: Limitations of Noisy Reversible Computation
Authors: D. Aharonov (Physics and CS, Hebrew Univ.) and M. Ben-Or(CS,Hebrew
  univ.) and R. Impagliazzo (CS, UCSD) and N. Nisan (CS, Hebrew univ.)
Comments: 13 pages
\\
  Noisy computation and reversible computation have been studied separately,
and it is known that they are as powerful as unrestricted computation. We study
the case where both noise and reversibility are combined and show that the
combined model is weaker than unrestricted computation. In our noisy reversible
circuits, each wire is flipped with probability p each time step, and all the
inputs to the circuit are present in time 0. We prove that any noisy reversible
circuit must have size exponential in its depth in order to compute a function
with high probability. This is tight as we show that any circuit can be
converted into a noise-resistant reversible one with a blow up in size which is
exponential in the depth. This establishes that noisy reversible computation
has the power of the complexity class NC^1.
  We extend this to quantum circuits(QC). We prove that any noisy QC which is
not worthless, and for which all inputs are present at time 0, must have size
exponential in its depth. (This high-lights the fact that fault tolerant QC
must use a constant supply of inputs all the time.) For the lower bound, we
show that quasi-polynomial noisy QC are at least powerful as logarithmic depth
QC, (or QNC^1). Making these bounds tight is left open in the quantum case.
\\


\\
Paper: quant-ph/9611029
From: Dorit Aharonov <>
Date: Sun, 17 Nov 1996 19:24:08 +0200 (IST)

Title: Polynomial Simulations of Decohered Quantum Computers
Authors: Dorit Aharonov (Physics and computer science, Hebrew Univ.) and
  Michael Ben-Or (Computer science, Hebrew univ.)
Comments: 12 pages
\\
  We define formally decohered quantum computers (using density matrices), and
present a simulation of them by a probabalistic classical Turing Machine. We
study the slowdown of the simulation for two cases: (1) sequential quantum
computers, or quantum Turing machines(QTM), and (2) parallel quantum computers,
or quantum circuits. This paper shows that the computational power of decohered
quantum computers depends strongly on the amount of parallelism in the
computation.
  The expected slowdown of the simulation of a QTM is polynomial in time and
space of the quantum computation, for any non zero decoherence rate. This means
that a QTM subjected to any amount of noise is worthless. For decohered quantum
circuits, the situation is more subtle and depends on the decoherence rate,
eta. We find that our simulation is efficient for circuits with decoherence
rate higher than some constant, but exponential for general circuits with
decoherence rate lower than some other constant. Using computer experiments, we
show that the transition from exponential cost to polynomial cost happens in a
short range of decoherence rates, and exhibit the phase transitions in various
quantum circuits.
\\

***For most problems, computing time expands on an exponential scale with
complexity for classical computers, to have a polynomial law on QC is very
interesting, untinkably large calculations become possible.****

\\
Paper: quant-ph/9611031
From: "Hoi-Kwong Lo" <>
Date: Tue, 19 Nov 1996 10:08:47 +0000

Title: Insecurity of Quantum Secure Computations
Author: Hoi-Kwong Lo
Comments: 26 pages, revtex
\\
  It had been widely claimed that quantum mechanics can protect private
information during public decision in for example the so-called two-party
secure computation. If this were the case, quantum smart-cards could prevent
fake teller machines from learning the PIN (Personal Identification Number)
from the customers' input. Although such optimism has been challenged by the
recent surprising discovery of the insecurity of the so-called quantum bit
commitment, the security of quantum two-party computation itself remains
unaddressed. Here we answer this question directly by showing that all
``one-sided'' two-party computations (which allow only one of the two parties
to learn the result) are necessarily insecure. As corollaries to our results,
quantum oblivious password identification and the so-called quantum
one-out-of-two oblivious transfer are impossible. We also construct a class of
functions that cannot be computed securely in any ``two-sided'' two-party
computation. Nevertheless, quantum cryptography remains useful in key
distribution and can still provide partial security in ``quantum money''
proposed by Wiesner.
\\


\\
Paper: quant-ph/9611041
From: Bruno Huttner <>
Date: Mon, 25 Nov 1996 09:08:11 +0100 (MET)

Title: Quantum Cloning, Eavesdropping and Bell's inequality
Authors: N. Gisin and B. Huttner (Group of Applied Physics, University of
  Geneva)
Comments: LaTex, 13 pages, with 6 Postscript figures
\\
  We analyze various eavesdropping strategies on a quantum cryptographic
channel. We present the optimal strategy for an eavesdropper restricted to a
two-dimensional probe, interacting on-line with each transmitted signal. The
link between safety of the transmission and the violation of Bell's inequality
is discussed. We also use a quantum copying machine for eavesdropping and for
broadcasting quantum information.
\\

*** Quantum copy is very near teleportation of the structure of an object:
Repair one molecule and you can copy it to all similar molecules dammaged in a
body***

\\
Paper: quant-ph/9611042
From: Bruno Huttner <>
Date: Mon, 25 Nov 1996 10:41:28 +0100 (MET)

Title: ``Plug and play'' systems for quantum cryptography
Authors: A. Muller, T. Herzog, B. Huttner, W. Tittel, H. Zbinden and N. Gisin
  (Group of Applied Physics, University of Geneva)
Comments: LaTex, 6 pages, with 2 Postscript figures, Submitted to Applied
  Physics Letters
\\
  We present a time-multiplexed interferometer based on Faraday mirrors, and
apply it to quantum key distribution. The interfering pulses follow exactly the
same spatial path, ensuring very high stability and self balancing. Use of
Faraday mirrors compensates automatically any birefringence effects and
polarization dependent losses in the transmitting fiber. First experimental
results show a fringe visibility of 0.9984 for a 23km-long interferometer,
based on installed telecom fibers.
\\


\\
Paper: quant-ph/9611046
From: Asher Peres <>
Date: Mon, 25 Nov 1996 16:11:11 -0800

Title: Error correction and symmetrization in quantum computers
Authors: Asher Peres
Comments: 18 pages LaTeX + 1 figure PostScript. Proceedings of PhysComp'96
  workshop, Boston 21-24 November 1996, to appear in Physica D (1997)
\\
  Errors in quantum computers are of two kinds: sudden perturbations to
isolated qubits, and slow random drifts of all the qubits. The latter may be
reduced, but not eliminated, by means of symmetrization, namely by using many
replicas of the computer, and forcing their joint quantum state to be
completely symmetric. On the other hand, isolated errors can be corrected by
quantum codewords that represent a logical qubit in a redundant way, by several
physical qubits. If one of the physical qubits is perturbed, for example if it
gets entangled with an unknown environment, there still is enough information
encoded in the other physical qubits to restore the logical qubit, and
disentangle it from the environment. The recovery procedure may consist of
unitary operations, without the need of actually identifying the error.
\\


**** I hope this information is not too scientific for cryonics***.


		Yvan Bozzonetti.


Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=7280