[Please email me if you can answer my questions below! I still don't
know the answers. ---TYC]
========================================================================
X-Coding-System: undecided-unix
From: tchow@lsa.umich.edu
Newsgroups: sci.math.research
Subject: Oracles for quantum computers
Message-ID: <9r1q8q$h5e$1@galois.mit.edu>
Originator: tchow@laguerre.mit.edu.mit.edu (Timothy Chow)
Approved: Daniel Grayson , moderator for sci.math.research
Lines: 40
Date: 22 Oct 2001 18:58:34 GMT
NNTP-Posting-Host: 130.126.108.30
X-Complaints-To: abuse@uiuc.edu
X-Trace: vixen.cso.uiuc.edu 1003789691 130.126.108.30 (Mon, 22 Oct 2001 17:28:11 CDT)
NNTP-Posting-Date: Mon, 22 Oct 2001 17:28:11 CDT
Organization: University of Illinois at Urbana-Champaign
I am trying to understand "Strengths and weaknesses of quantum computing"
by Bennett, Bernstein, Brassard, and Vazirani.
http://arxiv.org/abs/quant-ph/9701001
There are some key points that I am stuck on. I have tried to contact the
authors (see the email reproduced below) but without success. I would be
grateful if someone could clear up my confusion. Thank you in advance!
----------------------------------------------------------------------------
My friend and I have been trying to understand your very interesting paper
"Strengths and weaknesses of quantum computing." A couple of points have
been causing us trouble and we were hoping that you could clear them up.
The copy I am working from is quant-ph/9701001; I hope this is not very
different from the SIAM J. Computing version.
The main question I have has to do with the proof of Theorem 3.1. The
proof compares the behavior of M with respect to two different oracles
A and A_i. There appears to be a tacit assumption that M^A and M^{A_i}
will be identical until time i. But I do not see why this has to be true.
Conceivably, there could be oracle queries much earlier than time i on
which A and A_i differ, and this could cause significant divergence in
the (superposed) states of the two machines.
Related to this, the proof of Theorem 3.5 talks about a machine M^A that
runs in time at most T(n). Is there a tacit assumption that M^A runs in
time at most T(n) for *all* length-preserving oracles A? In principle,
the runtimes could be different for different oracles.
Finally, the abstract says that NP cannot be solved in on QTM in time
o(2^{n/2}) relative to an oracle chosen uniformly at random. But the
proofs seem to deal only with *length-preserving* oracles. Isn't this
a weaker result?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences