1 of 25

Quantum Computing

Sergey Tikhomirov

Lecture 5

​

https://sites.google.com/site/sergeytikhomirov/teaching/2025-quantum

​

​

WhatsApp group

https://chat.whatsapp.com/DWCoppTR6yu57qR5hDtt36

​

​

sergey.tikhomirov@gmail.com

2 of 25

Review of Lecture 4

 

3 of 25

Entanglement

  •  

 

4 of 25

Entanglement

  • Table

​

​

​

​

​

​

​

​

  • CNOT-the most entangling operator
  • Composition on entangling could be non-entagling

5 of 25

Universal gates

  •  

6 of 25

C-C-U gate

  •  

7 of 25

Implementation of classical algorithms on quantum computers

  • Postulate 1:�Any classical reversible computation can be reduced to use of classical C-XOR (C-C-NOT)
  • Postulate 2:�Any classical computation on n bits can be implemented reversibly with at most n ancilla bits
  • Consequence: �Any classical algorithm on n bits can be implemented an quantum computer with 2n qbits
  • Special importance of C-C-NOT��

8 of 25

Quantum circuit.

​

​

Width – number of qbits

Size – number of gates

Length – minimal number of operations taking into account parallelization

Number of CNot operators

9 of 25

From scheme to matrix notation.

​

​

 

10 of 25

C-C-U Operator

  •  

11 of 25

C-C-U Operator. Remarks

  •  

12 of 25

 

  •  

13 of 25

 

  •  

14 of 25

 

  •  

15 of 25

 

  •  

16 of 25

 

  •  

17 of 25

 

  •  

18 of 25

 

  •  

19 of 25

Quantum permutation|k> -> |k+1>

A lot of ancilla qbit

r5

r4

r3

r2

0

q5

q4

q3

q2

q1

​

​

​

​

​

 

20 of 25

 

​

​

​

​

​

​

  • We discussed how to continue this to C-C-C-…-X?�How many 2-qbit operations we will use?
  • Does there exists other options?�

21 of 25

Quantum Permutation.|k> -> |k+1>

One ancilla qbit. Idea

 

 

Problems:

It works only if ancilla is in state |0>�After applying the circuit ancilla qbit does not preserve state |0>�For each division operation we will need an extra ancilla

Trick: Uncompute

22 of 25

C-C-…-C-Not implementation with (n-2) ancilla

23 of 25

Fast C-…-C-Not

​

​

​

​

​

 

24 of 25

CCCC-U gate representation

 

25 of 25

C-C-U Operator

  •