A Good Tutorial

• [A] L.R. Rabiner "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition" (30 pages)
  A good examples (1) Simple "3-stste Markov model of whether" as observable Markov model; (2) Coin toss model whichis either observable or hidden depending on scenario; and (3) Urn and ball model as Hidden Markov model. (2) is described as "Three possible Markov models which can account for the results of hidden coin tossing experiments, i.e., 1-coin/2-coin/3-coin models"
  
  
  
  
  
  
  
  • "Besides, because no one has ever built a quantum computer, there is no way any direct comparison can be made at this time. It is up to the reader to decide which approach holds the most promise."
  • "Almost twenty years ago Richard Feynman observed that classical computers could not simulate certain quantum mechanical effects such as entanglement [3]."

• [B] "An Introduction to Quantum Computing for Non-Physicists" (45 pages)
  
  • The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne by physisits.
  • "Accessing the results is equivalent to making a measurement, which disturbs the quantum state."
  • "a register of n qubits can be in a superposition of all 2^n possible values."
  • "only one classical bit's worth of information can be extracted from a qubit."
  • "all quantum state transformations have to be reversible. While the classical NOT gate is reversible, AND, OR and NAND gates are not. Thus it is not obvious that quantum transformations can carry out all classical computations."
  • "Boyer et.al. [Boyer et al. 1996] provide a detailed analysis of the performance of Grover' algorithm."
    • BOYER, M., BRASSARD, G., HOYER, P., AND TAPP, A. 1996. Tight bounds on quantum search. In Proceedings of the Workshop on Physics of Computation: PhysComp '96 (Los Alamitos, CA, 1996). Institute of Electrical and Electronic Engineers Computer Society Press. Preprint at Los Alamos Physics reprint Archive, http://xxx.lanl.gov/abs/quant-ph/9605034. => OK
  • "Quantum error correction must reconstruct the exact encoded quantum state. Given the impossibility of cloning or copying the quantum state, this reconstruction appears harder than in the classical case. However, it turns out that classical techniques can be modified to work for quantum systems."
  • "Decoherence, the distortion of the quantum state due to interaction with the environment, is a key problem."
  • "ColinWilliams and Scott Clearwater�fs book Explorations in QuantumComputing [Williams and Clearwater 1998] comes with software, in the form of Mathematica notebooks, that simulates some quantum algorithms like Shor's algorithm"

• [C] I. Carneiro, M. Loo, X. Xu, M. Girerd, V Kendon, and P. L. Knight (2005) "Entanglement in coined quantum walks on regular graphs" New Journal of Physics Vol. 7, pp 156--185 (29 pages)
  
  • The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne by physisits.
  • "For an overview of the development of quantum walks for quantum computing, see the recent reviews by Kempe [6] and Ambainis [7]. " [6] Kempe J 2003 Contemp. Phys. 44 302.27 (Preprint quant-ph/0303081) [7] Ambainis A 2003 Int. J. Quantum Inform. 1 507 (Preprint quant-ph/0403120)
  • "we address this issue by investigating the evolution of the quantum mechanical entanglement as the quantum walk progresses."
  • "Since the range of higher-dimensional coin operators is too large for systematic numerical study, for the remainder of this paper we concentrate on two natural choices" --- Grover's and DFT coins.
  • "The Grover operator was first introduced by Moore and Russell [25] in their study of quantumwalks on the hypercube." [25] Moore C and Russell A 2002 Proc. 6th Int. Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM �f02) ed J D P Rolim and S Vadhan (Berlin: Springer) pp 164.78 (Preprint quant-ph/0104137)

Approaches to A-Needle-in-a-Haystack

• [D] "Quantum Mechanics helps in searching for a needle in a haystack" Grover (4 pages)
  • "Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names."
  • "See [D1] & [D3] for a more detailed introduction to quantum computers."

Search a Needle in Conputer Science

• [D3] Lov K. Grover (1996) "A fast quantum mechanical algorithm for database search" Proceedings, STOC, pp. 212-219. (8 pages) --- An updated version of this paper can be found in a world-wide-web page.
  
  Not found a concret example of aneedle-in-a-haystack but found a next interesting phrase.
  • "quantum mechanical systems can simultaneously be in multiple Schrodinger cat states and carry out multiple tasks at the same time."

• [D5] M. Boyer, G. Brassard, P. Hoyer, and A. Tapp (1996) "Tight Bounds on Quantum Searching" 4th Workshop on Physics and computation (17 pages)
  
  Authors briefly showed "three simple applications for Grover's algorithm" as (1) Database searching problem; (2) Cryptographic application; and (3) Boolean formula on n variables.

• [D9] G. Brassard (1997) "Searching a quantum phone book" Science, pp. 627-628. ...
  
  No concrete example of searching for needle except for criptography problem, either

Can GP simulate Quantum Computation?

• [E] L. Spector H. Barnum, H. J. Bernstein, and N. Swamy (1996) "Finding a Better-than-Classical Quantum AND/OR Algorithm using Genetic Programming" Proceedings, of the 1999 Conhgress on Evolutionary computation. (8 pages)
  • "For those new to quantum computing Steane provides a good overview [E7], Braunstein provides an accessible on-line tutorial [E8], Williams and Clearwater provide a text with a CD ROM containing Mathematica code for simulating quantum computers [E9], and Milburn provides an introduction for the general reader [E10]." [E7] A. Steane, .Quantum computing,. Reports on Progress in Physics, vol. 61, pp. 117.173, 1998, http://xxx.lanl.gov/abs/quant-ph/9708022. [E8] S. L. Braunstein, .Quantum computation: a tutorial, . Available only electronically, on-line at URL http ://chemphys.weizmann.ac.il/ ~schmuel/comp/comp.html, 1995. [E9] C. P.Williams and S. H. Clearwater, Explorations in Quantum Computing, Springer-Verlag, TELOS, 1997. [E10] G. J. Milburn, Schr�Nodinger�fs Machines: The Quantum Technology Reshaping Everyday Life, W. H. Freeman & Co., 1997.
  • "Because practical quantum computer hardware is not yet available, we must test the tness of evolved quantum algorithms using a quantum computer simulator that runs on conventional computer hardware. This entails an exponential slowdown, so we must be content to simulate relatively small systems."
  • "The basic unit of information in a quantum computer is a qubit, which is like a classical bit except that a qubit can exist in a superposition of states and can become entangled with other qubits.that is, its value can be linked to the values of other qubits in non-classical ways."
  • "We will give a fuller treatment of the quantum mechanics of these algorithms in a future article." (Now we can check what has happened via google search for example.)

Quantum Walks

• (authors) "(title)" (? pages)