| 1 zirkus | Just what is quantum computation ? | maandag 17 september 2001 6:17 |
| 2 V.Z.Nuri |
Re: Just what is quantum computation ? | maandag 24 september 2001 2:45 |
Hi, the following question/issue that I raise is somewhat rhetorical in that I don't expect anyone here to be able to address it, but perhaps someone will think of something.
In his foundational work [1] on quantum computation (QC), David Deutsch proposed two models for QC: quantum circuit families and quantum Turing machines (QTM) which are supposed to be computationally equivalent.
However, paper [2] argues that QC is not equivalent to QTM computation because the selective measurement process essential to QC is "extraneous to the causal notions of both algorithm and dynamics" (from page 11 of [2]).
Furthermore, the possibility is established [3] that QTMs and uniform quantum circuit families may not be computationally equivalent when implementing certain algorithms (i.e. Las Vegas algorithms).
M. Freedman et al. have proposed [4] a model of QC as modular functor which was supposed to have been equivalent to QTM and quantum circuit families for BQP (the class of functions computable with bounded error, given quantum resources, in polynomial time).
This still leaves me wondering just what is QC ?
[1] see e.g., D. Deutsch, Proc Roy Soc London, A400 (1985), 97-117
[2] http://arxiv.org/abs/quant-ph/0005069
[3] http://arxiv.org/abs/quant-ph/9906095
[4] see e.g. http://arxiv.org/abs/quant-ph/0001108
hi zirkus.. what a nice post complete with 4 refs..!!
deutsch is considered the founder/pioneer of QM computing given his seminal 85 paper, but even he would probably agree that it is not well defined yet, either in the theoretical or the physics realm. its very embryonic.
however the class BQP is probably now agreed on by theorists to represent QM computing physics. as for a "QTM", I dont think one has been defined yet...??
would be very interested to discuss this with scientific types such as yourself or others on theory-edge.. am tracking this field closely due to its revolutionary nature..
http://groups.yahoo.com/group/theory-edge/
hot quantum computing books/links Ive turned up from following it the last few yrs (its definitely heated up significantly just within last yr)
http://groups.yahoo.com/group/theory-edge/message/3166
very nice paper by bart selman, "one complexity theorists view of quantum computing"
http://groups.yahoo.com/group/theory-edge/message/2456
knill/laflamme at los alamos have done a 7qbit machine.. state of the art right now.. nice NYT article.. note the military industrial complex is *very* interested & funding some of the research (including the NSA!!!)
http://www.nytimes.com/2001/03/27/science/27QUAN.html
very recent wired article
http://www.wired.com/wired/archive/9.09/quantum.html
australian govt initiative to fund qm computing race, linked to los alamos
http://groups.yahoo.com/group/theory-edge/message/1616
nsf funding qm computing fabrication
http://www.eet.com/story/OEG20010703S0022
zirkus
[2] http://arxiv.org/abs/quant-ph/0005069
[3] http://arxiv.org/abs/quant-ph/9906095
[4] see e.g. http://arxiv.org/abs/quant-ph/0001108
Back to my home page Contents of This Document
>
[1] see e.g., D. Deutsch, Proc Roy Soc London, A400 (1985), 97-117
Created: 26 September 2001