QUANTUM COMPUTING - Bio-Inspired and Nanoscale Integrated Computing - page 67

3
QUANTUM COMPUTING
John H. Reif
Quantum computation (QC) is a type of computation where unitary and measure-
ment operations are executed on linear superpositions of basis states. This chapter
provides a brief introduction to QC. We begin with a discussion of basic models
for QC such as quantum TMs, quantum gates, and circuits and related complexity
results. We then discuss a number of topics in quantum information theory
including bounds for quantum communication and I/O complexity, methods for
quantum data compression and quantum error correction (that is, techniques for
decreasing decoherence errors in QC), Furthermore, we enumerate a number of
methodologies and technologies for doing QC. Finally, we discuss resource
bounds for QC including bonds for processing time, energy, and volume,
particularly emphasizing challenges in determining volume bounds for observa-
tion apparatus.
3.1. INTRODUCTION
3.1.1. Reversible Computations
Reversible computations are computations where each state transformation is a
reversible function, so that any computation can be reversed without loss of
information. Landauer [1] showed that irreversible computations must generate
heat in the computing process, and that reversible computations have the property
that if executed slowly enough, they (in the limit) can consume no energy in an
adiabatic computation. Bennett [2] (also see Bennett, Landauer [3], Landauer [4],
Toffoli [5]) showed that any computing machine (e.g., an abstract machine such as