1 of 32

Introduction to �Quantum Computing

​

COMS 4281 (Fall 2024)

​

Week 2: Reversible computing, basics of quantum info

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

2 of 32

Admin

  • Pset0 due Friday.

​

  • Change of Program period ends this Friday, September 13, 9:45pm

​

  • Pset1 out next week.

​

3 of 32

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

...

4 of 32

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.

​

​

​

​

​

​

​

​

​

​

​

​

5 of 32

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.

​

​

​

​

​

​

​

​

​

​

​

​

6 of 32

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.

7 of 32

Reversible classical information processing

  •  

 

8 of 32

Reversible classical information processing

  •  

 

 

9 of 32

Reversible classical information processing

  •  

 

 

10 of 32

Reversible classical information processing

  •  

 

 

11 of 32

Reversible classical information processing

  •  

 

 

12 of 32

Reversible classical information processing

  •  

 

 

 

13 of 32

Reversible classical information processing

  •  

 

 

14 of 32

Reversible classical information processing

  •  

 

 

 

 

15 of 32

Composite systems

  •  

 

 

 

 

16 of 32

Composite systems

  •  

 

 

 

 

 

 

17 of 32

Composite systems

  •  

 

 

 

 

 

18 of 32

Composite systems

  •  

 

 

 

 

 

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

19 of 32

Reversible computation

We can put many bits together to compute:

​

​

​

​

​

​

​

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

20 of 32

Reversible computation

We can describe reversible computation using a circuit diagram.

 

 

 

 

Time

n bit input

1 bit gates

Multi-bit gates

……

21 of 32

Reversible computation

Compute the final state of circuit:

 

 

 

 

CNOT gate

ctrl

tgt

NOT gate

​

 

 

 

22 of 32

Reversible computation

Compute the final state of circuit:

 

CNOT gate

ctrl

tgt

 

 

 

 

1

2

3

4

5

 

 

 

NOT gate

​

23 of 32

Universal computation with reversible circuits

  •  

 

 

 

 

 

…

…

 

 

 

 

 

 

…

24 of 32

Universal computation with reversible circuits

  •  

 

 

 

 

 

…

…

 

 

 

 

 

 

…

 

25 of 32

Reversible computing, linear algebra style

  •  

 

 

 

 

26 of 32

Transformation matrices

  •  

 

Matrix with exactly one 1 in �each column and row

 

27 of 32

Transformation matrices

  •  

 

 

28 of 32

Tensor products

  •  

29 of 32

Tensor products, representations

  •  

30 of 32

Tensor products, bits

  •  

 

Transformations:

​

​

 

 

 

31 of 32

Tensor products, bits

Vector representation of two bits:

​

​

 

 

 

 

 

Matrix representation of transformations:

​

​

 

 

32 of 32

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!