[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