Site Navigation
Home Basics of Quantum Mechanics Quantum Computing Applications About
Links
Shor's Algorithm Further Applications

Classical Computing

    At a fundamental level classical computing revolves around the use of Bits, a single 0 or 1 digit, and Logic Gates, which manipulate them. Logic gates take an input, typically in the form of 2 or more bits, and perform an operation on the, producing a single output. There are four basic logic gates:

    AND gate: Performs a logical and operation (if all input is true, the output is true).
    OR gate: Performs a logical or operation (if any input is true, the output is true).
    XOR gate: Outputs a true if one, but not more, of the inputs are true.
    NOT gate: Takes a single bit and returns the opposite value.

There are NOT versions of every previously listed logic gate, which invert the rest of those gates. In classical computing both inputs and outputs are discrete, and do not, practically speaking, have an uncertainty associated with them. These bits do not exist as waveforms until observed.
   
    In classical computing the amount of information you can store increases linearly as the number of bits increases; i.e if it takes 64 bits to store one number it will take N*64 bits to store N numbers.
    Classical computers can be summarized by the term deterministic. If the input is known, and the instructions are known, the output can be perfectly predicted.

Quantum Computing

  Basics:
    A computer with quantum circuits encodes information in the form of Qubits. Rather than existing as a zero or a one, qubits are 2-D vectors where each axis corresponds to a zero or a one, and the magnitude of each component corresponds to the probability that a qubit will exist as a particular value when collapsed via measurement. These bits are processed via Quantum Logic Gates. These gates are very different from those in classical computing. These gates, like classical gates, manipulate qubits, but they do not cause collapse; they maintain the superposition of the qubits entering them. As a result the produce vectors, not definite bits. There are many quantum gates. We will consider just two:
    Hadamard Gate: The Hadamard gate forces the possibilities that single qubit will collapse to either zero or 1 exactly equal. It is represented by the following matrix:



    CNOT Gate:  The CNOT gate takes two qubits and inverts (performs a NOT) on the second qubit when the first is a one. Remember these qubits exist in a state of superpostion, so all possible productions are performed. It is represented by the following matrix:

   
    Unlike classical computing all quantum logic gates are reversible; we know the exact input based on the output. There is a mathematical reason to this; all quantum logic gates can be represented as unitary matrices, meaning the transpose of the matrix is also the inverse of the matrix. So, by performing the transpose operation we can produce an identity matrix, and the input matrix.

What does this all mean?
    Quantum computing essential works like so. First you initialize, or set, as many registers (where bits/qubits are stored when not being processed) as you for the answer to a problem. Then you pass all of this through a circuit with quantum logic gates. This will first produce all possible answers to that problem, in the form of a vector space, and then proceed to perform matrix operations in the form of logic gates to remove incorrect answers. This sounds inefficient, but because the qubit can hold more information than a bit, it can be much more efficient for many problem.

Challenges:
    The trick to quantum computing is maintaining superpostion; if you're qubits are observed at the wrong time, they collapse. If they collapse you only have one answer out of the many you were producing, and it's likely it's incorrect. This problem of accidental collapse becomes more extreme as quantum computers become larger and more complex.
    One part of classical computing that is absolutely vital is what's known as assignment; we often want to clone a value, so we can perform operations on the original, but keep an unchanged copy. By the No-Cloning Theorem this simple mechanic is not achievable in quantum computing; qubits cannot be cloned.This makes the prospect of implementing everyday programs in a quantum computer, quite the headache.