GA's are a form of evolutionary computing, one of the three main branches of biologically inspired Artificial Intelligence, (the other two being Neural Networks and Machine Learning). In short, it is a computing model derived from the concept of evolution - a process which optimizes an initial set or population of potential solutions over time. As it is commonly promulgated, an initial population of some life form is, over time, optimized to fit the environment via random mutations, and the swap of genetic code passed from parents to offspring.

Evolution, then, as it is commonly modeled can be considered a method of searching a large search space, one which does not have to be static, but can be dynamic. It is also a massively parallel process - rather than work on one species at a time, evolution tests and changes a number of species in parallel. From a Computer Science perspective, then, evolution is just a probabilistic search algorithm which balances exploiting the best solution with exploring the whole search space.

Problems such as function optimization can be effectively solved with GA's by encoding an initial, randomly generated population of potential solutions and applying genetic operators such as reproduction, crossover and mutation to each successive generation (iteration of a program loop), until some stopping criterion is reached (i.e. a maximum number of generations, or a certain interval of precision). Potential solutions are usually encoded as binary strings (i.e. 1001001), in GA literature usually denoted as a chromosome.

Reproduction is simply the act of choosing the best candidates from a set of possible solutions via a weighted average. Crossover is the mating of two strings (the "swapping" of genetic code) to produce two offspring (e.g. Parent1 = 10010 and Parent2 = 11001, where the crossover site is randomly chosen to be after the second bit, then Child1 = 10001 and Child2 = 11010). Mutation is the random flipping of a bit (i.e. a 1 to 0, 0 to 1). It can be shown that variability of these three genetic operators effectively "explores" a search space, while at the same time honing in on the best solutions.

For more information, consult the resources below.

Essentially the framework by which all physical theories are believed (by most) to reside in. It was developed in the early part of the 20th century by Planck, Bohr, Einstein, Heisenberg, Schrodinger, Born and others, arising at a time when there were some crises in physics. In certain experiments, what was predicted by classical physics (i.e. all the physics before the 'quantum age') gave contradictory results in the lab. Early quantum theory thus arose to patch the inconsistencies appearing in physics. This evolved into the mathematical formalism of Quantum Mechanics, and was soon extended and fused with Special Relativity to become what is commonly known as Quantum Field Theory.

Quantum mechanical effects are only noticeable on the atomic scale, and as the system we study gets larger, the laws of quantum mechanics "simplify" into the laws of classical physics. Often noted by scientist and laymen alike, quantum laws are non-intuitive; they embody concepts that are not wholly reconcilable with the ingrained 'classical world' physical ideas we are used to. This same conundrum is visible in the conceptual understanding of Special Relativity - it's effects are only noticeable for those speeds close to that of light. In fact, there exists are large body of research devoted to interpretations of quantum mechanics.

The strange new concepts ushered in by quantum theory are numerous. Early on it was noticed that quantisation of quantum systems was the norm - energy was not continuous but took on discrete amounts of energy called quanta. Matter was both a particle and a wave, and thus could take on many of the characteristics of waves, such as superposition and the associated concept of interference. Measurements made on atomic systems disturbed a system, so one could never be sure of both a particle's momentum and position at the same time - Heisenberg's famous Uncertainty Principle. In fact the outcome of measurements was not even deterministic, but probabilistic. Another strange occurence, the ability of particles to be non-locally correlated in the sense that a measurement made on one will affect the other no matter the distance, demonstrated by the so-called Schrodinger's Cat thought experiment, is an example of quantum entanglement.

For more information, consult the resources below.

Information, it must be noted, is stored by matter and thus must follow the laws of physics. The written word is usually stored on paper, in the form of ink on paper, or particles on other particles. The bit of a computer is stored on a magnetized disk. Our memories and thoughts are encoded (as some believe) in RNA protein strands in our brain. Thus Claude Shannon's mathematical ideas of his Information Theory have a physical counterpart. In short then, information is physical. Now, if we try to store information on smaller and smaller objects, eventually quantum effects will take over (note that this is not merely a thought exercise, but will eventually be of practical interest, as demonstrated by "Moore's Law"). Thus ultimately, the theory of physical information is contained within what is called Quantum Information Theory.

Thus we can say that a Quantum Computer is a device that performs computations which take advantage of the features of quantum mechanics. It turns out that quantum computers seem to perform quite well on problems thought intractable by classical computers - namely factoring numbers as demonstrated by Shor's Algorithm. A quantum computer is not even based on classical logic, but Quantum Logic and instead of classical bits (binary digits), they operate on Qubits (Quantum Bits - a quantum superposition of state vectors 1 and 0 and everything in between).

While theoretically, quantum information theory and its applications to quantum computers have been developed quite extensively, the practical implementations for such devices remain dubious. Some of the leading practical implementation proposals include:

• NMR (Nuclear Magnetic Resonance): The use a testube of molecules of the same type, and manipulation of the spin of each nucleus via applications of magnetic pulses. Qubits are establish through the entanglement of these spins by the chemical bonds between neighboring atoms.
• Quantum Dots: A solid state implementation - essentially one or more electrons trapped in a 'cage' of atoms. Computations may involve manipulation of charge, spin or energy state. A quantum computer would conceivably be an array of such quantum dots, where a qubit would be an entanglement of energy states within a dot.
• Ion Trap: One or more individual ions are 'trapped' in an electromagnetic field, and are cooled until their motions are negligible. Each ion is manipulated by a laser pulse to acheive an entanglement of low and high energy spin states, which is a qubit.
• Josephson Junction: A sandwiching of a thin layer of non-superconducting material between two pieces of superconducting material. Electrons travelling through the superconductors tunnel through the nonsuperconducting region - in fact the probabilities of where the electrons will tunnel to is manipulated by the application of a voltage across the junction - providing a means to create qubits.

For more information, consult the resources below.

Quantum computers operate on qubits, which are essentially systems exhibiting quantum entaglement. However, entangled systems are extremely fragile and will eventually interact with the environment and break down - a process called decoherence. The possible errors that may occur in such a system are not only bit flip erros (0 to 1, 1 to 0) but also phase errors. In addition, the situation is complicated even further by the fact that quantum systems cannot be copied, the so-called No Cloning Theorem. To combat decoherence then, Quantum Error Correcting Codes are are used.

For more information, consult the resources below.

• Goldberg, David. Genetic Algorithms in Search, Optimization and Machine Learning.
• Mitchell, Melanie. An Introduction to Genetic Algorithms.
• Feynman, Richard. The Feynman Lectures on Physics (volume 3).
• Messiah, Albert. Quantum Mechanics.
• Preskill, John. Physics 219 / Computer Science 219 Lecture Notes (Quantum Computation).
• Meglicki, Zdzislaw. Introduction to Quantum Computing Notes (M743).

• Quantum Information Science Group at UofT
• A General Introduction to Genetic Algorithms
• GALib - A C++ Library of Genetic Algorithm Components by Matthew Wall
• Basics of Information Theory
• Entropy on the WWW
• A Mathematical Overview of Quantum Mechanics
• A Collection of Articles on Quantum Computing (for non-specialists)
• A Brief History of Quantum Computing
• A Technical Tutorial on Quantum Computing
• Quantum Computation and Quantum Information Theory WebSeminar
• An Introduction to Quantum Error Correction
• Quantum Computer Simulators