Introduction to �Quantum Computing

​

COMS 4281 (Fall 2022)

​

Week 1: The physics of information, and reversible computing

Course homepage: http://www.henryyuen.net/classes/fall2022

Roadmap

• Landauer’s insight: reversibility of physics implies reversibility of computation

​

• Principles of reversible computing

​

• Universal computing with reversible circuits

​

• Linear algebra formulation of reversible computing

The physics of information

• In (classical) computing, we see operations like

​

​

​

​

• Information appears to be erased.

​

• Is this actually possible? Can information… disappear?

​

​

​

...

A = 0 #reset

...

Reversibility of physics

• The laws of physics – both quantum and classical – are inherently �reversible.

​

• Any isolated physical process running in one direction, can �(in principle) run in reverse.

​

• In fact: at a microscopic level, one should not be able to tell the �difference between time running forwards or backwards.

​

​

​

​

​

​

​

​

​

​

​

​

Reversibility of physics

• Even the process of an egg falling and breaking is (in principle) �reversible and possible according to physics.

​

• However, in the macroscopic world such events are �extremely unlikely.

​

• Unlikely because we are relatively near the Big Bang, which was a �low-entropy initial state of the universe.

​

​

​

​

​

​

​

​

​

​

​

​

​

Reversibility of computation

• In 1960s the physicist Rolf Landauer had a simple but powerful observation:

​

• Computation is a physical process.
• Physical processes are fundamentally reversible.
• Therefore, computation can be performed reversibly.

​

• This observation led to study of reversible�computing, which later influenced the �study of quantum computing.

Reversible classical information processing

Reversible classical information processing

Reversible classical information processing

Reversible classical information processing

Reversible classical information processing

Reversible classical information processing

Reversible classical information processing

Reversible classical information processing

Composite systems

Composite systems

Composite systems

Composite systems

First bit ( “control bit”) controls �if second bit (“target bit”) gets flipped.

Reversible computation

We can put many bits together to compute:

​

​

​

​

​

​

​

Computation: a sequence of pre-determined transformations on �specified subsystems.

Reversible computation

We can describe reversible computation using a circuit diagram.

Time

n bit input

1 bit gates

Multi-bit gates

……

Reversible computation

Compute the final state of circuit:

CNOT gate

ctrl

tgt

NOT gate

​

Reversible computation

Compute the final state of circuit:

CNOT gate

ctrl

tgt

1

2

3

4

5

NOT gate

​

Universal computation with reversible circuits

…

…

…

Universal computation with reversible circuits

…

…

…

Reversible computing, linear algebra style

Transformation matrices

Matrix with exactly one 1 in �each column and row

Transformation matrices

Tensor products

Tensor products, representations

Tensor products, examples

Matrix representation of transformations:

​

​

Summary

• Landauer’s insight: reversibility of physics implies reversibility of computation

​

• Principles of reversible computing

​

• Universal computing with reversible circuits

​

• Linear algebra formulation of reversible computing

​

• Next: quantum information!