Quantum Computing

• This exponential growth in number of states, together with the ability to subject the entire space to transformations (either unitary dynamical evolution of the system, or a measurement projection into an eigenvector subspace), provides the foundation for quantum computing.
• An interesting (apparent) dilemma is the energetic costs/irreversability of classical computing. Since unitary transformations are invertible, quantum computations (except measurements) will all be reversible. Most classical boolean operations such as $b_1\land b_2$, $b_1\lor b_2$, and $b_1\land\negthickspace\negthickspace\negmedspace\negthinspace\sim b_2$ are irreversible, and therefore cannot directly be used as basic operations for quantum computers.

• The logical nand-gate ( $b_1\land\negthickspace\negthickspace\negmedspace\negthinspace\negthinspace\sim b_2$) is sufficient to generate all the traditional boolean functions (e.g., $\sim\negmedspace b \equiv b\ \land\negthickspace\negthickspace\negmedspace\negthinspace\sim b$). We are likely to end up looking for simple quantum gates that are similarly generic for quantum operations.

• In general, if we had enough time, we could simulate any quantum computation with a classical computer. The real potential value of quantum computers lies in speeding up computations. The critical questions are:

  1.

  How much can we speed up particular computations?

  2.

  Can we develop a practical implementation of a particular quantum computation?

  3.

  Can we build a physical implementation of a quantum computer?

  4.

  Does the implementation allow us to carry out useful computations before decoherence interactions with the environment disturb the system too much?

  5.

  Given the ``no cloning'' principle, can we develop quantum error detection/correction systems? In particular, we can't just take measurements for error control since measurements have irreversible effects on quantum systems.