CS计算机代考程序代写 algorithm MULT20015 Elements of Quantum Computing

MULT20015 Elements of Quantum Computing
Lecture 7

Subject outline

Lecture topics (by week)

1 – Introduction to quantum computing and maths basics
2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Classical complexity and simple quantum algorithms
6 – Cryptography and Shor’s quantum factoring algorithm
7 – Post quantum cryptography and quantum key distribution
8 – Quantum search algorithms
9 – Quantum algorithms for option pricing
10 – Optimisation problems on quantum computers
11 – Portfolio optimisation using quantum computers
12 – Quantum machine learning

Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8

MULT20015 Elements of Quantum Computing
Lecture 7

Week 4

Lecture 7
7.1 Binary notation with multiple qubits
7.2 Quantum Registers
7.3 Hadamard gates and equal superposition
7.4 Quantum “Parallelism”
7.5 Multiqubit measurement
7.6 Toffoli gate

Lecture 8
8.1 Classical digital logic and universality
8.2 Reversible logic
8.3 Arithmetic operations on a quantum computer
8.4 Universality in quantum computing

Practice class 4
Multi-qubit states and operations

MULT20015 Elements of Quantum Computing
Lecture 7

Lecture 6 recap: two-qubit logic and entanglement

Rule: The target is flipped
iff the control qubit is “1”.

a |00i+ b |01i+ c |10i+ d |11i
! a |00i+ b |01i+ d |10i+ c |11i

AAACbHicdZHbSsNAEIY3UavWUzzcibBYLIJQEhHsZcEbLxWsLTSlTDbbdunmwO5EKaGvKfgA3voEXrhJK2jVgYWPf+Znhn+DVAqNrvtq2Sura5X1jc3q1vbO7p6zf/Cok0wx3maJTFQ3AM2liHkbBUreTRWHKJC8E0xuin7niSstkvgBpynvRzCKxVAwQCMNnLROgfoTjrnrzugFDebsFcxK9ko9nLPRfb9ap74SozGCUsnz//7wm599+QdOzW24ZdHf4C2gRhZ1N3De/DBhWcRjZBK07nluiv0cFAom+azqZ5qnwCYw4j2DMURc9/MymRk9M0pIh4kyL0Zaqt8dOURaT6PATEaAY73cK8S/er0Mh81+LuI0Qx6z+aJhJikmtIiZhkJxhnJqAJgS5lbKxqCAofmMH1sCBSaaIhdvOYXf8HjZ8NyGd39VazUXCW2QY3JKzolHrkmL3JI70iaMvJAPa82qWO/2kX1sn8xHbWvhOSQ/yq5/Akl6tzA=AAACbHicdZHbSsNAEIY3UavWUzzcibBYLIJQEhHsZcEbLxWsLTSlTDbbdunmwO5EKaGvKfgA3voEXrhJK2jVgYWPf+Znhn+DVAqNrvtq2Sura5X1jc3q1vbO7p6zf/Cok0wx3maJTFQ3AM2liHkbBUreTRWHKJC8E0xuin7niSstkvgBpynvRzCKxVAwQCMNnLROgfoTjrnrzugFDebsFcxK9ko9nLPRfb9ap74SozGCUsnz//7wm599+QdOzW24ZdHf4C2gRhZ1N3De/DBhWcRjZBK07nluiv0cFAom+azqZ5qnwCYw4j2DMURc9/MymRk9M0pIh4kyL0Zaqt8dOURaT6PATEaAY73cK8S/er0Mh81+LuI0Qx6z+aJhJikmtIiZhkJxhnJqAJgS5lbKxqCAofmMH1sCBSaaIhdvOYXf8HjZ8NyGd39VazUXCW2QY3JKzolHrkmL3JI70iaMvJAPa82qWO/2kX1sn8xHbWvhOSQ/yq5/Akl6tzA=AAACbHicdZHbSsNAEIY3UavWUzzcibBYLIJQEhHsZcEbLxWsLTSlTDbbdunmwO5EKaGvKfgA3voEXrhJK2jVgYWPf+Znhn+DVAqNrvtq2Sura5X1jc3q1vbO7p6zf/Cok0wx3maJTFQ3AM2liHkbBUreTRWHKJC8E0xuin7niSstkvgBpynvRzCKxVAwQCMNnLROgfoTjrnrzugFDebsFcxK9ko9nLPRfb9ap74SozGCUsnz//7wm599+QdOzW24ZdHf4C2gRhZ1N3De/DBhWcRjZBK07nluiv0cFAom+azqZ5qnwCYw4j2DMURc9/MymRk9M0pIh4kyL0Zaqt8dOURaT6PATEaAY73cK8S/er0Mh81+LuI0Qx6z+aJhJikmtIiZhkJxhnJqAJgS5lbKxqCAofmMH1sCBSaaIhdvOYXf8HjZ8NyGd39VazUXCW2QY3JKzolHrkmL3JI70iaMvJAPa82qWO/2kX1sn8xHbWvhOSQ/yq5/Akl6tzA=AAACbHicdZHbSsNAEIY3UavWUzzcibBYLIJQEhHsZcEbLxWsLTSlTDbbdunmwO5EKaGvKfgA3voEXrhJK2jVgYWPf+Znhn+DVAqNrvtq2Sura5X1jc3q1vbO7p6zf/Cok0wx3maJTFQ3AM2liHkbBUreTRWHKJC8E0xuin7niSstkvgBpynvRzCKxVAwQCMNnLROgfoTjrnrzugFDebsFcxK9ko9nLPRfb9ap74SozGCUsnz//7wm599+QdOzW24ZdHf4C2gRhZ1N3De/DBhWcRjZBK07nluiv0cFAom+azqZ5qnwCYw4j2DMURc9/MymRk9M0pIh4kyL0Zaqt8dOURaT6PATEaAY73cK8S/er0Mh81+LuI0Qx6z+aJhJikmtIiZhkJxhnJqAJgS5lbKxqCAofmMH1sCBSaaIhdvOYXf8HjZ8NyGd39VazUXCW2QY3JKzolHrkmL3JI70iaMvJAPa82qWO/2kX1sn8xHbWvhOSQ/yq5/Akl6tzA=

Rule: the phase of the target
flipped iff the control qubit is “1”.

a |00i+ b |01i+ c |10i+ d |11i
! a |00i+ b |01i+ c |10i � d |11i

AAACbHicjZHbSsNAEIY38VxP9XBXhMViEcSSiGAvBW+8rGC10IQy2W7bpZsDuxOlhL6m4AN46xN44SYNeKgXDix8/DM/M/wbJFJodJxXy15aXlldW9+obG5t7+xW9/YfdJwqxjsslrHqBqC5FBHvoEDJu4niEAaSPwaTm7z/+MSVFnF0j9OE+yGMIjEUDNBI/WrSoEC9CcfMcWb0jAZzdnNmBbuFPpiz0T2v0qCeEqMxglLx83/851/+frXuNJ2i6CK4JdRJWe1+9c0bxCwNeYRMgtY910nQz0ChYJLPKl6qeQJsAiPeMxhByLWfFcnM6IlRBnQYK/MipIX63ZFBqPU0DMxkCDjWv3u5+Fevl+Kw5WciSlLkEZsvGqaSYkzzmOlAKM5QTg0AU8LcStkYFDA0n/FjS6DARJPn4v5OYREeLpqu03TvLuvXrTKhdVIjx+SUuOSKXJNb0iYdwsgL+bBWrFXr3T60a/bRfNS2Ss8B+VF24xNMsLcyAAACbHicjZHbSsNAEIY38VxP9XBXhMViEcSSiGAvBW+8rGC10IQy2W7bpZsDuxOlhL6m4AN46xN44SYNeKgXDix8/DM/M/wbJFJodJxXy15aXlldW9+obG5t7+xW9/YfdJwqxjsslrHqBqC5FBHvoEDJu4niEAaSPwaTm7z/+MSVFnF0j9OE+yGMIjEUDNBI/WrSoEC9CcfMcWb0jAZzdnNmBbuFPpiz0T2v0qCeEqMxglLx83/851/+frXuNJ2i6CK4JdRJWe1+9c0bxCwNeYRMgtY910nQz0ChYJLPKl6qeQJsAiPeMxhByLWfFcnM6IlRBnQYK/MipIX63ZFBqPU0DMxkCDjWv3u5+Fevl+Kw5WciSlLkEZsvGqaSYkzzmOlAKM5QTg0AU8LcStkYFDA0n/FjS6DARJPn4v5OYREeLpqu03TvLuvXrTKhdVIjx+SUuOSKXJNb0iYdwsgL+bBWrFXr3T60a/bRfNS2Ss8B+VF24xNMsLcyAAACbHicjZHbSsNAEIY38VxP9XBXhMViEcSSiGAvBW+8rGC10IQy2W7bpZsDuxOlhL6m4AN46xN44SYNeKgXDix8/DM/M/wbJFJodJxXy15aXlldW9+obG5t7+xW9/YfdJwqxjsslrHqBqC5FBHvoEDJu4niEAaSPwaTm7z/+MSVFnF0j9OE+yGMIjEUDNBI/WrSoEC9CcfMcWb0jAZzdnNmBbuFPpiz0T2v0qCeEqMxglLx83/851/+frXuNJ2i6CK4JdRJWe1+9c0bxCwNeYRMgtY910nQz0ChYJLPKl6qeQJsAiPeMxhByLWfFcnM6IlRBnQYK/MipIX63ZFBqPU0DMxkCDjWv3u5+Fevl+Kw5WciSlLkEZsvGqaSYkzzmOlAKM5QTg0AU8LcStkYFDA0n/FjS6DARJPn4v5OYREeLpqu03TvLuvXrTKhdVIjx+SUuOSKXJNb0iYdwsgL+bBWrFXr3T60a/bRfNS2Ss8B+VF24xNMsLcyAAACbHicjZHbSsNAEIY38VxP9XBXhMViEcSSiGAvBW+8rGC10IQy2W7bpZsDuxOlhL6m4AN46xN44SYNeKgXDix8/DM/M/wbJFJodJxXy15aXlldW9+obG5t7+xW9/YfdJwqxjsslrHqBqC5FBHvoEDJu4niEAaSPwaTm7z/+MSVFnF0j9OE+yGMIjEUDNBI/WrSoEC9CcfMcWb0jAZzdnNmBbuFPpiz0T2v0qCeEqMxglLx83/851/+frXuNJ2i6CK4JdRJWe1+9c0bxCwNeYRMgtY910nQz0ChYJLPKl6qeQJsAiPeMxhByLWfFcnM6IlRBnQYK/MipIX63ZFBqPU0DMxkCDjWv3u5+Fevl+Kw5WciSlLkEZsvGqaSYkzzmOlAKM5QTg0AU8LcStkYFDA0n/FjS6DARJPn4v5OYREeLpqu03TvLuvXrTKhdVIjx+SUuOSKXJNb0iYdwsgL+bBWrFXr3T60a/bRfNS2Ss8B+VF24xNMsLcy

Rule: the qubits states are swapped.
a |00i+ b |01i+ c |10i+ d |11i
! a |00i+ c |01i+ b |10i+ d |11i

AAACbHicbZHbSsNAEIY38VxP9XAnwmKxCEJJRLCXgjdeVrAqNKFMNtt26ebA7kQpoa8p+ADe+gReuElz0doOLHz8Mz8z/BukUmh0nC/LXlvf2Nza3qnt7u0fHNaPjl90kinGuyyRiXoLQHMpYt5FgZK/pYpDFEj+Gowfiv7rO1daJPEzTlLuRzCMxUAwQCP162mTAvXGHHPHmdJrGszYLZiV7JZ6OGOje16tST0lhiMEpZKPRT+b8wer/P16w2k5ZdFlcCtokKo6/fq3FyYsi3iMTILWPddJ0c9BoWCST2tepnkKbAxD3jMYQ8S1n5fJTOmlUUI6SJR5MdJSnXfkEGk9iQIzGQGO9P9eIa7q9TIctP1cxGmGPGazRYNMUkxoETMNheIM5cQAMCXMrZSNQAFD8xkLWwIFJpoiF/d/CsvwctNynZb7dNu4b1cJbZMzckGuiEvuyD15JB3SJYx8kl9rw9q0fuxT+8w+n43aVuU5IQtlN/8ASXq3MA==AAACbHicbZHbSsNAEIY38VxP9XAnwmKxCEJJRLCXgjdeVrAqNKFMNtt26ebA7kQpoa8p+ADe+gReuElz0doOLHz8Mz8z/BukUmh0nC/LXlvf2Nza3qnt7u0fHNaPjl90kinGuyyRiXoLQHMpYt5FgZK/pYpDFEj+Gowfiv7rO1daJPEzTlLuRzCMxUAwQCP162mTAvXGHHPHmdJrGszYLZiV7JZ6OGOje16tST0lhiMEpZKPRT+b8wer/P16w2k5ZdFlcCtokKo6/fq3FyYsi3iMTILWPddJ0c9BoWCST2tepnkKbAxD3jMYQ8S1n5fJTOmlUUI6SJR5MdJSnXfkEGk9iQIzGQGO9P9eIa7q9TIctP1cxGmGPGazRYNMUkxoETMNheIM5cQAMCXMrZSNQAFD8xkLWwIFJpoiF/d/CsvwctNynZb7dNu4b1cJbZMzckGuiEvuyD15JB3SJYx8kl9rw9q0fuxT+8w+n43aVuU5IQtlN/8ASXq3MA==AAACbHicbZHbSsNAEIY38VxP9XAnwmKxCEJJRLCXgjdeVrAqNKFMNtt26ebA7kQpoa8p+ADe+gReuElz0doOLHz8Mz8z/BukUmh0nC/LXlvf2Nza3qnt7u0fHNaPjl90kinGuyyRiXoLQHMpYt5FgZK/pYpDFEj+Gowfiv7rO1daJPEzTlLuRzCMxUAwQCP162mTAvXGHHPHmdJrGszYLZiV7JZ6OGOje16tST0lhiMEpZKPRT+b8wer/P16w2k5ZdFlcCtokKo6/fq3FyYsi3iMTILWPddJ0c9BoWCST2tepnkKbAxD3jMYQ8S1n5fJTOmlUUI6SJR5MdJSnXfkEGk9iQIzGQGO9P9eIa7q9TIctP1cxGmGPGazRYNMUkxoETMNheIM5cQAMCXMrZSNQAFD8xkLWwIFJpoiF/d/CsvwctNynZb7dNu4b1cJbZMzckGuiEvuyD15JB3SJYx8kl9rw9q0fuxT+8w+n43aVuU5IQtlN/8ASXq3MA==AAACbHicbZHbSsNAEIY38VxP9XAnwmKxCEJJRLCXgjdeVrAqNKFMNtt26ebA7kQpoa8p+ADe+gReuElz0doOLHz8Mz8z/BukUmh0nC/LXlvf2Nza3qnt7u0fHNaPjl90kinGuyyRiXoLQHMpYt5FgZK/pYpDFEj+Gowfiv7rO1daJPEzTlLuRzCMxUAwQCP162mTAvXGHHPHmdJrGszYLZiV7JZ6OGOje16tST0lhiMEpZKPRT+b8wer/P16w2k5ZdFlcCtokKo6/fq3FyYsi3iMTILWPddJ0c9BoWCST2tepnkKbAxD3jMYQ8S1n5fJTOmlUUI6SJR5MdJSnXfkEGk9iQIzGQGO9P9eIa7q9TIctP1cxGmGPGazRYNMUkxoETMNheIM5cQAMCXMrZSNQAFD8xkLWwIFJpoiF/d/CsvwctNynZb7dNu4b1cJbZMzckGuiEvuyD15JB3SJYx8kl9rw9q0fuxT+8w+n43aVuU5IQtlN/8ASXq3MA==

|00i+ |11i
p
2

6= (a |0i+ b |1i)⌦ (c |0i+ d |1i)
AAACW3icbZBLSwMxFIXT8V1fVXHlJliEilASEXQpuHGpYFXolJJJ72hoJjNN7ghlmJ/nj3Dh0pVb3Zs+xOeFwOGceznhizKtHDL2VAlmZufmFxaXqssrq2vrtY3Na5fmVkJLpjq1t5FwoJWBFirUcJtZEEmk4Sbqn43ymwewTqXmCocZdBJxZ1SspEBvdWvdMLZCFjTsAxaMlfRgIjkvaVmEbmCxOCxLGhoY0IYYh5T5rWgi+T4NU1QJONqQX2nvM+3W6qzJxkP/Cj4VdTKdi27tJeylMk/AoNTCuTZnGXYKYVFJDWU1zB1kQvbFHbS9NMJXd4oxiJLueadH49T6Z5CO3e8XhUicGyaR30wE3rvf2cj8L2vnGJ90CmWyHMHISVGca4opHVGlPWVBoh56IaRV/q9U3gtPFj37Hy2RFZ5M6bnw3xT+iuvDJmdNfnlUPz2ZElokO2SXNAgnx+SUnJML0iKSPJJX8kbeK8/BTFANViarQWV6s0V+TLD9AU0Vstk=AAACW3icbZBLSwMxFIXT8V1fVXHlJliEilASEXQpuHGpYFXolJJJ72hoJjNN7ghlmJ/nj3Dh0pVb3Zs+xOeFwOGceznhizKtHDL2VAlmZufmFxaXqssrq2vrtY3Na5fmVkJLpjq1t5FwoJWBFirUcJtZEEmk4Sbqn43ymwewTqXmCocZdBJxZ1SspEBvdWvdMLZCFjTsAxaMlfRgIjkvaVmEbmCxOCxLGhoY0IYYh5T5rWgi+T4NU1QJONqQX2nvM+3W6qzJxkP/Cj4VdTKdi27tJeylMk/AoNTCuTZnGXYKYVFJDWU1zB1kQvbFHbS9NMJXd4oxiJLueadH49T6Z5CO3e8XhUicGyaR30wE3rvf2cj8L2vnGJ90CmWyHMHISVGca4opHVGlPWVBoh56IaRV/q9U3gtPFj37Hy2RFZ5M6bnw3xT+iuvDJmdNfnlUPz2ZElokO2SXNAgnx+SUnJML0iKSPJJX8kbeK8/BTFANViarQWV6s0V+TLD9AU0Vstk=AAACW3icbZBLSwMxFIXT8V1fVXHlJliEilASEXQpuHGpYFXolJJJ72hoJjNN7ghlmJ/nj3Dh0pVb3Zs+xOeFwOGceznhizKtHDL2VAlmZufmFxaXqssrq2vrtY3Na5fmVkJLpjq1t5FwoJWBFirUcJtZEEmk4Sbqn43ymwewTqXmCocZdBJxZ1SspEBvdWvdMLZCFjTsAxaMlfRgIjkvaVmEbmCxOCxLGhoY0IYYh5T5rWgi+T4NU1QJONqQX2nvM+3W6qzJxkP/Cj4VdTKdi27tJeylMk/AoNTCuTZnGXYKYVFJDWU1zB1kQvbFHbS9NMJXd4oxiJLueadH49T6Z5CO3e8XhUicGyaR30wE3rvf2cj8L2vnGJ90CmWyHMHISVGca4opHVGlPWVBoh56IaRV/q9U3gtPFj37Hy2RFZ5M6bnw3xT+iuvDJmdNfnlUPz2ZElokO2SXNAgnx+SUnJML0iKSPJJX8kbeK8/BTFANViarQWV6s0V+TLD9AU0Vstk=AAACW3icbZBLSwMxFIXT8V1fVXHlJliEilASEXQpuHGpYFXolJJJ72hoJjNN7ghlmJ/nj3Dh0pVb3Zs+xOeFwOGceznhizKtHDL2VAlmZufmFxaXqssrq2vrtY3Na5fmVkJLpjq1t5FwoJWBFirUcJtZEEmk4Sbqn43ymwewTqXmCocZdBJxZ1SspEBvdWvdMLZCFjTsAxaMlfRgIjkvaVmEbmCxOCxLGhoY0IYYh5T5rWgi+T4NU1QJONqQX2nvM+3W6qzJxkP/Cj4VdTKdi27tJeylMk/AoNTCuTZnGXYKYVFJDWU1zB1kQvbFHbS9NMJXd4oxiJLueadH49T6Z5CO3e8XhUicGyaR30wE3rvf2cj8L2vnGJ90CmWyHMHISVGca4opHVGlPWVBoh56IaRV/q9U3gtPFj37Hy2RFZ5M6bnw3xT+iuvDJmdNfnlUPz2ZElokO2SXNAgnx+SUnJML0iKSPJJX8kbeK8/BTFANViarQWV6s0V+TLD9AU0Vstk=

CNOT

Controlled-Z (CZ)

SWAP

Entanglement: e.g. Bell-state can’t be written as a product
QUI: computes
entanglement
entropy (EE)

MULT20015 Elements of Quantum Computing
Lecture 7

7.1 Binary notation with multiple qubits

MULT20015
Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7

Recall from Lecture 1: Multi qubits – state counting

1 qubit:

|0ñ, |1ñ

2 qubits:

|0ñ, |1ñ |0ñ, |1ñ

Binary combinations

|00ñ, |01ñ, |10ñ, |11ñ

|0ñ, |1ñ

3 qubits:

|0ñ, |1ñ |0ñ, |1ñ

|000ñ, |001ñ, |010ñ, |011ñ
|100ñ, |101ñ, |110ñ, |111ñ

|0ñ, |1ñ

4 qubits:

|0ñ, |1ñ |0ñ, |1ñ |0ñ, |1ñ |0ñ, |1ñ

|0000ñ, |0001ñ, |0010ñ, |0011ñ
|0100ñ, |0101ñ, |0110ñ, |0111ñ
|1000ñ, |1001ñ, |1010ñ, |1011ñ
|1100ñ, |1101ñ, |1110ñ, |1111ñ

binary representation of decimals 0 to 1

binary representation of decimals 0 to 3

binary representation of decimals 0 to 7

binary representation of decimals 0 to 15

MULT20015 Elements of Quantum Computing
Lecture 7

Binary Notation with n qubits

Binary Decimal

000 0

001 1

010 2

011 3

100 4

101 5

110 6

111 7

Quantum computers, like classical computers,
store numbers in binary.

Left: All the states possible for three
bit/qubits.

If there are n qubits, then the number of
possible states is:

N = 2n
AAACAXicbVDLSgNBEOz1GeMr6tHLYBA8hd2omIsQ8OJJIpgHJGuYnUySIbOzy0yvEJac/AKv+gXexKtf4gf4H04eB5NY0FBUddPdFcRSGHTdb2dldW19YzOzld3e2d3bzx0c1kyUaMarLJKRbgTUcCkUr6JAyRux5jQMJK8Hg5uxX3/i2ohIPeAw5n5Ie0p0BaNopfoduSbFR9XO5d2COwFZJt6M5GGGSjv30+pELAm5QiapMU3PjdFPqUbBJB9lW4nhMWUD2uNNSxUNufHTybkjcmqVDulG2pZCMlH/TqQ0NGYYBrYzpNg3i95Y/M9rJtgt+alQcYJcsemibiIJRmT8O+kIzRnKoSWUaWFvJaxPNWVoE5rbEmg64DiyuXiLKSyTWrHgnRcu7y/y5dIsoQwcwwmcgQdXUIZbqEAVGAzgBV7hzXl23p0P53PauuLMZo5gDs7XL2vAlt4=

Specifically the integers,

0 .. 2n � 1
AAACDHicbVDLSsNAFL3xWesr6tLNYBHcGJKq2GXBjcsK9gFNLJPptB06mYSZSaGE/oJf4Fa/wJ249R/8AP/DaZuFbT1w4XDOvZzLCRPOlHbdb2ttfWNza7uwU9zd2z84tI+OGypOJaF1EvNYtkKsKGeC1jXTnLYSSXEUctoMh3dTvzmiUrFYPOpxQoMI9wXrMYK1kTq27foIOQ7yUflJoEvkdeyS67gzoFXi5aQEOWod+8fvxiSNqNCEY6XanpvoIMNSM8LppOiniiaYDHGftg0VOKIqyGafT9C5UbqoF0szQqOZ+vciw5FS4yg0mxHWA7XsTcX/vHaqe5UgYyJJNRVkHtRLOdIxmtaAukxSovnYEEwkM78iMsASE23KWkgJJR5SPTG9eMstrJJG2fGunJuH61K1kjdUgFM4gwvw4BaqcA81qAOBEbzAK7xZz9a79WF9zlfXrPzmBBZgff0CzzmZAA==

MULT20015 Elements of Quantum Computing
Lecture 7

Binary and Decimal Notation

In general we use two representations in the QUI (N = 2n):

Binary:

Decimal:

| i =
X

�

a� |�i

a� = |a�|ei✓�

| i = a0…00 |0…00i+ a0…01 |0…01i+ a0…10 |0…10i+ …+ a1…1 |1…1i

| i = a0 |0i+ a1 |1i+ a2 |2i+ …+ aN�1 |N � 1i

MULT20015 Elements of Quantum Computing
Lecture 7

Memory needed on a classical computer

If we use 128 bits (16 B) per complex number, then we need:

Qubits Dimension (2n) Memory required

1 2 256 bits = 32 B

2 4 64 B

6 64 1 kB

10 1,024 16 kB

20 1,048,576 16 MB

30 1,073,741,824 16 GB

40 1,099,511,627,776 16 TB

50 1,125,899,906,842,624 16 PB

60 1,152,921,504,606,846,976 16 EB

Memory required to store the quantum state of different numbers of qubits
grows exponentially.

MULT20015 Elements of Quantum Computing
Lecture 7

7.2 Quantum Registers

MULT20015
Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7

Quantum Registers

We will often need to consider several different qubits grouped together. A group
of several qubits is known as a register.

|0i

…

|0i

Several qubits Quantum register

MULT20015 Elements of Quantum Computing
Lecture 7

Multiple registers

|xi
AAACAXicbVDJSgNBEK2JW4xb1KOXxiB4CjMumGPAi8cIZoFkCD2dmqSZnoXuHjEMOfkFXvULvIlXv8QP8D/sJHMwiQ8KHu9VUVXPSwRX2ra/rcLa+sbmVnG7tLO7t39QPjxqqTiVDJssFrHseFSh4BE2NdcCO4lEGnoC215wO/XbjygVj6MHPU7QDekw4j5nVBup3QtQkyfSL1fsqj0DWSVOTiqQo9Ev//QGMUtDjDQTVKmuYyfazajUnAmclHqpwoSygA6xa2hEQ1RuNjt3Qs6MMiB+LE1FmszUvxMZDZUah57pDKkeqWVvKv7ndVPt19yMR0mqMWLzRX4qiI7J9Hcy4BKZFmNDKJPc3ErYiErKtEloYYsnqUlmYnJxllNYJa2LqnNZvb6/qtRreUJFOIFTOAcHbqAOd9CAJjAI4AVe4c16tt6tD+tz3lqw8pljWID19QtShZdt

|yi
AAACAHicbVDJSgNBEK2JW4xb1KOXxiB4CjMumGPAi8cIZoFkCD2dnqRNz0J3jTAMufgFXvULvIlX/8QP8D/sJHMwiQ8KHu9VUVXPi6XQaNvfVmFtfWNzq7hd2tnd2z8oHx61dJQoxpsskpHqeFRzKULeRIGSd2LFaeBJ3vbGt1O//cSVFlH4gGnM3YAOQ+ELRtFIrd6YI0n75YpdtWcgq8TJSQVyNPrln94gYknAQ2SSat117BjdjCoUTPJJqZdoHlM2pkPeNTSkAdduNrt2Qs6MMiB+pEyFSGbq34mMBlqngWc6A4ojvexNxf+8boJ+zc1EGCfIQzZf5CeSYESmr5OBUJyhTA2hTAlzK2EjqihDE9DCFk9RE8zE5OIsp7BKWhdV57J6fX9VqdfyhIpwAqdwDg7cQB3uoAFNYPAIL/AKb9az9W59WJ/z1oKVzxzDAqyvX/n0l0Q=

|zi
AAACAHicbVDLSgNBEOz1GeMr6tHLYBA8hV0fmGPAi8cI5gHJEmYnk2TM7Owy0yvEJRe/wKt+gTfx6p/4Af6Hk2QPJrGgoajqprsriKUw6Lrfzsrq2vrGZm4rv72zu7dfODismyjRjNdYJCPdDKjhUiheQ4GSN2PNaRhI3giGNxO/8ci1EZG6x1HM/ZD2legJRtFK9faQI3nqFIpuyZ2CLBMvI0XIUO0UftrdiCUhV8gkNabluTH6KdUomOTjfDsxPKZsSPu8ZamiITd+Or12TE6t0iW9SNtSSKbq34mUhsaMwsB2hhQHZtGbiP95rQR7ZT8VKk6QKzZb1EskwYhMXiddoTlDObKEMi3srYQNqKYMbUBzWwJNbTBjm4u3mMIyqZ+XvIvS1d1lsVLOEsrBMZzAGXhwDRW4hSrUgMEDvMArvDnPzrvz4XzOWlecbOYI5uB8/QL7i5dF

| i = |xi |yi |zi
AAACHHicbVDLSsNAFL3xWesr6tLNYBFclcQHdiMU3LisYB/QhDKZTtqhkwczEzGGbv0Mv8CtfoE7cSv4Af6H0yYL23pguIdz7uXeOV7MmVSW9W0sLa+srq2XNsqbW9s7u+befktGiSC0SSIeiY6HJeUspE3FFKedWFAceJy2vdH1xG/fUyFZFN6pNKZugAch8xnBSks9EzkjqpATS4aucv6QlzQvjz2zYlWtKdAisQtSgQKNnvnj9COSBDRUhGMpu7YVKzfDQjHC6bjsJJLGmIzwgHY1DXFApZtNfzJGx1rpIz8S+oUKTdW/ExkOpEwDT3cGWA3lvDcR//O6ifJrbsbCOFE0JPkiP+FIRWgSC+ozQYniqSaYCKZvRWSIBSZKhzezxRNYBzPWudjzKSyS1mnVPqte3J5X6rUioRIcwhGcgA2XUIcbaEATCDzBC7zCm/FsvBsfxmfeumQUMwcwA+PrF4YjoRA=

And of course you can have superpositions over these states as well. An example:

| i = |xi ⌦ |yi ⌦ |zi
AAACLHicbVDLSsNAFJ34rPUVdelmsAiuSuIDuxEKblxWsA9oQplMJ+3QyYOZGzGG/oaf4Re41S9wI+JSv8NpmoVtPTBw7rn3cu4cLxZcgWV9GEvLK6tr66WN8ubW9s6uubffUlEiKWvSSESy4xHFBA9ZEzgI1oklI4EnWNsbXU/67XsmFY/CO0hj5gZkEHKfUwJa6pmWM2KAnVhxfIVz/oCdCHjA1LRMZ8vHnlmxqlYOvEjsglRQgUbP/Hb6EU0CFgIVRKmubcXgZkQCp4KNy06iWEzoiAxYV9OQaC83y382xsda6WM/kvqFgHP170ZGAqXSwNOTAYGhmu9NxP963QT8mpvxME6AhXRq5CcCQ4QnMeE+l4yCSDUhVHJ9K6ZDIgkFHeaMiyeJDmasc7HnU1gkrdOqfVa9uD2v1GtFQiV0iI7QCbLRJaqjG9RATUTRE3pBr+jNeDbejU/jazq6ZBQ7B2gGxs8vcHenyg==

| i =
1

2
|1i |5i+

2
|1i |6i+

1
p
2
|3i |8i

AAACY3icdVFbS8MwGM3qfd7q9E2E4BAEYbSbl70Igi8+KrhNWMtIs3SGpReTr8Io/Yn+AH/AfoGvCqZdH9zUAyGHc87HF068WHAFlvVeMZaWV1bX1jeqm1vbO7vmXq2rokRS1qGRiOSTRxQTPGQd4CDYUywZCTzBet74Nvd7r0wqHoWPMImZG5BRyH1OCWhpYI6cMQPsxIrja+z4ktDUztJmhnNd0+K6yPDZv+blnOmoFwk6UmZas0w7G5h1q2EVwL+JXZI6KnE/MKfOMKJJwEKggijVt60Y3JRI4FSwrOokisWEjsmI9TUNScCUmxaFZPhEK0PsR1KfEHCh/pxISaDUJPB0MiDwrBa9XPzL6yfgt92Uh3ECLKSzRX4iMEQ4bxcPuWQUxEQTQiXXb8X0mehuQP/B3BZPEt1M3ou92MJv0m027Fbj4uG8ftMuG1pHh+gYnSIbXaEbdIfuUQdR9IY+0Cf6qkyNTaNmHMyiRqWc2UdzMI6+AU9iuuw=

As before, if

i,j

|aij |2 = 1
AAACFXicbZDLSsNAFIYnXmu9RV2Jm8EiuJCSVMVuhIIblxXsBdoYJtNJO+1MEmYmQkmDj+ETuNUncCduXfsAvofTNgvb+sPAx3/O4Zz5vYhRqSzr21haXlldW89t5De3tnd2zb39ugxjgUkNhywUTQ9JwmhAaooqRpqRIIh7jDS8wc243ngkQtIwuFfDiDgcdQPqU4yUtlzzsC1j7ib0rJ/CEdLQT0cPJXgNbdcsWEVrIrgIdgYFkKnqmj/tTohjTgKFGZKyZVuRchIkFMWMpPl2LEmE8AB1SUtjgDiRTjL5QgpPtNOBfij0CxScuH8nEsSlHHJPd3KkenK+Njb/q7Vi5ZedhAZRrEiAp4v8mEEVwnEesEMFwYoNNSAsqL4V4h4SCCud2swWT6ABUanOxZ5PYRHqpaJ9Xry8uyhUyllCOXAEjsEpsMEVqIBbUAU1gMETeAGv4M14Nt6ND+Nz2rpkZDMHYEbG1y9GKZ7i

| i =
X

aij |ii |ji
AAACJnicbVDLSsNAFJ3UV62vqEs3g0UQFyXxgd0IBTcuK9gHNCFMppN22pkkzEyEEvoPfoZf4Fa/wJ2IOzf+h9MkC9t6YLiHc+7l3jl+zKhUlvVllFZW19Y3ypuVre2d3T1z/6Ato0Rg0sIRi0TXR5IwGpKWooqRbiwI4j4jHX98O/M7j0RIGoUPahITl6NBSAOKkdKSZ545Y6KgE0sKb6AjE+6ldDSFKC+ZSfMy8syqVbMywGViF6QKCjQ988fpRzjhJFSYISl7thUrN0VCUczItOIkksQIj9GA9DQNESfSTbM/TeGJVvowiIR+oYKZ+nciRVzKCfd1J0dqKBe9mfif10tUUHdTGsaJIiHOFwUJgyqCs4BgnwqCFZtogrCg+laIh0ggrHSMc1t8gXQwU52LvZjCMmmf1+yL2tX9ZbVRLxIqgyNwDE6BDa5BA9yBJmgBDJ7AC3gFb8az8W58GJ95a8koZg7BHIzvXy9dpaI=

then

MULT20015 Elements of Quantum Computing
Lecture 7

7.3 Hadamard gates and equal superposition

MULT20015
Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7

One Hadamard Gate

H|0i | i
AAACA3icbVDLSgNBEOyNrxhfUY9eBoPgKez6wBwDXjxGMA/JLmF2MpsMmZldZmaFsOToF3jVL/AmXv0QP8D/cJLswSQWNBRV3XR3hQln2rjut1NYW9/Y3Cpul3Z29/YPyodHLR2nitAmiXmsOiHWlDNJm4YZTjuJoliEnLbD0e3Ubz9RpVksH8w4oYHAA8kiRrCx0qM/ogb5iWa9csWtujOgVeLlpAI5Gr3yj9+PSSqoNIRjrbuem5ggw8owwumk5KeaJpiM8IB2LZVYUB1ks4Mn6MwqfRTFypY0aKb+nciw0HosQtspsBnqZW8q/ud1UxPVgozJJDVUkvmiKOXIxGj6PeozRYnhY0swUczeisgQK0yMzWhhS6iwzWZic/GWU1glrYuqd1m9vr+q1Gt5QkU4gVM4Bw9uoA530IAmEBDwAq/w5jw7786H8zlvLTj5zDEswPn6BVKKmJE=

As we’ve seen before, this produces an equal superposition:

| i = H |0i

=
|0i+ |1i

p
2

AAACYXicbVFNaxsxEJU3/Ujcr216zEXUNJQWzK5LSS6BQC85plAnAcuYWXnWEdZqN9JswIj9hf0FOYf+gF7bS7X2HvLRAcHTe280w1NWaeUoSW560daTp8+eb+/0X7x89fpN/Hb3zJW1lTiWpS7tRQYOtTI4JkUaLyqLUGQaz7Plt1Y/v0brVGl+0KrCaQELo3IlgQI1i1FkuFDG45UBa2H1qemLJZIXlVMN3z/a5ye8JXjChei3dy5yC9J35OeNmjZeuCtLftQ0rVGgmd95cxYPkmGyLv4YpB0YsK5OZ/EvMS9lXaAhqcG5SZpUNPVgSUmNYcfaYQVyCQucBGigQDf16zga/iEwc56XNhxDfM3e7fBQOLcqsuAsgC7dQ60l/6dNasoPp16ZqiY0cjMorzWnkrfZ8rmyKEmvAgBpVdiVy0sIaVH4gXtTMgshtjaX9GEKj8HZaJh+GX79PhocH3YJbbM99p59ZCk7YMfshJ2yMZPsJ/vN/rC/vdtoJ4qj3Y016nU979i9ivb+AekRt24=

MULT20015 Elements of Quantum Computing
Lecture 7

Two Hadamard Gates

H|0i
| i

AAACA3icbVDLSgNBEOyNrxhfUY9eBoPgKez6wBwDXjxGMA/JLmF2MpsMmZldZmaFsOToF3jVL/AmXv0QP8D/cJLswSQWNBRV3XR3hQln2rjut1NYW9/Y3Cpul3Z29/YPyodHLR2nitAmiXmsOiHWlDNJm4YZTjuJoliEnLbD0e3Ubz9RpVksH8w4oYHAA8kiRrCx0qM/ogb5iWa9csWtujOgVeLlpAI5Gr3yj9+PSSqoNIRjrbuem5ggw8owwumk5KeaJpiM8IB2LZVYUB1ks4Mn6MwqfRTFypY0aKb+nciw0HosQtspsBnqZW8q/ud1UxPVgozJJDVUkvmiKOXIxGj6PeozRYnhY0swUczeisgQK0yMzWhhS6iwzWZic/GWU1glrYuqd1m9vr+q1Gt5QkU4gVM4Bw9uoA530IAmEBDwAq/w5jw7786H8zlvLTj5zDEswPn6BVKKmJE=

This produces:

H|0i

| i = H ⌦H |00i

✓
|0i+ |1i

p
2

◆
⌦
✓
|0i+ |1i

p
2

◆

=
|00i+ |01i+ |10i+ |11i

=
|0i+ |1i+ |2i+ |3i

2
AAADIniclVLLattAFB2pr9R9xGmX3Qw1CWkDRqNQkk0h0I2XKdRJwGPMaHxlD5ZGysxVwAj9QT+jX9Bt+wXdla4K3fY/OrIVO69NLwgO5zF3OJooT5TFIPjt+ffuP3j4aONx68nTZ88321svTmxWGAl9mSWZOYuEhURp6KPCBM5yAyKNEjiNZh9q/fQCjFWZ/oTzHIapmGgVKynQUaMtb5tHMFG6hHMtjBHzt1WLzwBLnltV0Z33O7THM1QpWNqjCyUIKsp5q5YoTyDGXR4bIctapAHdW7goq0puzw2WYVVxoyZTfEMvD/rP1HLX0r6+wl4D2QqyNctYVdHwzujas0LhCu1fxjjo8ZVORu1O0A0WQ28D1oAOaeZ41P7Lx5ksUtAoE2HtgAU5DkthUMkEXMeFhVzImZjAwEEtXC/DcvE/K7rtmDGNM+M+jXTBXk2UIrV2nkbOmQqc2ptaTd6lDQqMD4el0nmBoOVyUVwkFDNaPw46VgYkJnMHhDTK3ZXKqXDloXtC17ZERri+6l7YzRZug5Owy/a77z6GnaPDpqEN8oq8JruEkQNyRHrkmPSJ9D57X71v3nf/i//D/+n/Wlp9r8m8JNfG//MPtDr5Fg==

We have used
digital notation
here

MULT20015 Elements of Quantum Computing
Lecture 7

Three Hadamard Gates

H|0i

| i
AAACA3icbVDLSgNBEOyNrxhfUY9eBoPgKez6wBwDXjxGMA/JLmF2MpsMmZldZmaFsOToF3jVL/AmXv0QP8D/cJLswSQWNBRV3XR3hQln2rjut1NYW9/Y3Cpul3Z29/YPyodHLR2nitAmiXmsOiHWlDNJm4YZTjuJoliEnLbD0e3Ubz9RpVksH8w4oYHAA8kiRrCx0qM/ogb5iWa9csWtujOgVeLlpAI5Gr3yj9+PSSqoNIRjrbuem5ggw8owwumk5KeaJpiM8IB2LZVYUB1ks4Mn6MwqfRTFypY0aKb+nciw0HosQtspsBnqZW8q/ud1UxPVgozJJDVUkvmiKOXIxGj6PeozRYnhY0swUczeisgQK0yMzWhhS6iwzWZic/GWU1glrYuqd1m9vr+q1Gt5QkU4gVM4Bw9uoA530IAmEBDwAq/w5jw7786H8zlvLTj5zDEswPn6BVKKmJE=

This produces:

H|0i

| i = H ⌦H ⌦H |0i |0i |0i

✓
|0i+ |1i

p
2

◆
⌦
✓
|0i+ |1i

p
2

◆
⌦

✓
|0i+ |1i

p
2

◆

=
|000i+ |001i+ |010i+ |011i+ |100i+ |101i+ |110i+ |111i

2
p
2

=
|0i+ |1i+ |2i+ |3i+ |4i+ |5i+ |6i+ |7i

2
p
2

AAAD3XicvZLPb9MwFMfdhB+j/FgHRy4WFdMAqYozxnZBmsSBHYdEt0l1VTmu01pNnMx+GaqsHLkhrvxt3Ljwf+C2UZp2O/OkKB+9933+Ws8vyhNpIAh+tzz/3v0HD3cetR8/efpst7P3/MJkheaiz7Mk01cRMyKRSvRBQiKuci1YGiXiMpp9WtQvb4Q2MlNfYZ6LYcomSsaSM3Cp0V7rD43ERCorrhXTms3flm06E4BpbiTe/7iPzzDNQKbCbBCmeCkLtn+0vWiiiYjhANNYM26r0ruVhpSWmmsNNixLquVkCm/qc/9TW3XHWm6DICirDsdkzaSRJ+s8aehJQ08aeuL0pQ1r97ts1+KawpoOa3pf01FNH2o63rBpU6HGjdfEo0436AXLwLeBVNBFVZyPOn/pOONFKhTwhBkzIEEOQ8s0SJ4IZ1AYkTM+YxMxcKiYe4KhXa5iiV+7zBjHmXafArzMNjssS42Zp5FTpgymZru2SN5VGxQQnwytVHkBQvGVUVwkGDK82Gs8llpwSOYOGNfS3RXzKXOjBrf9Gy6RZm5spZsL2Z7CbbgIe+Swd/Ql7J6eVBPaQS/RK3SACDpGp+gMnaM+4t5nL/VuvG/+yP/u//B/rqReq+p5gTbC//UPMck0/g==

MULT20015 Elements of Quantum Computing
Lecture 7

Hadamard gates and decimal notation

H⊗n|0i

H|0i

…

n qubits

| i =
|0i+ |1i

p
2

⌦
|0i+ |1i

p
2

…⌦
|0i+ |1i

p
2

i.e. even superposition over binary rep of integers: i = 0 to 2n – 1

| i =


1
p
2

�n
(|00…0i+ …+ |11…1i)

shorthand notation

| i =
1

2n/2

2n�1X

i=0

|ii
AAACNnicbZDLSgMxFIYz9VbrbdSlm2AR3FhnqmIRCgU3LivYC3TakkkzbWgmMyQZoYR5Fx/DJ3CrWzfuilsfwfSysK0/BH7+cw7n5PNjRqVynE8rs7a+sbmV3c7t7O7tH9iHR3UZJQKTGo5YJJo+koRRTmqKKkaasSAo9Blp+MP7Sb3xTISkEX9So5i0Q9TnNKAYKRN17TtvSBT0YklhGXqBQFi7qS52NL8spin0ZBJ2NS07aceEHF5A14RmRNO0a+edgjMVXDXu3OTBXNWuPfZ6EU5CwhVmSMqW68SqrZFQFDOS5rxEkhjhIeqTlrEchUS29fSPKTwzSQ8GkTCPKzhN/05oFEo5Cn3TGSI1kMu1SfhfrZWooNTWlMeJIhzPFgUJgyqCE2CwRwXBio2MQVhQcyvEA2RAKYN1YYsvkCEz4eIuU1g19WLBvSrcPF7nK6U5oSw4AafgHLjgFlTAA6iCGsDgBbyBd/BhvVpf1tj6nrVmrPnMMViQ9fMLLperqg==

Equal superposition of
states

MULT20015 Elements of Quantum Computing
Lecture 7

7.4 Quantum “Parallelism”

MULT20015
Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7

Calculating some function, f

|xi
AAACAHicbVDLSgNBEJz1GeMr6tHLYBA8hV0RzDHgxWME84BkCbOT3mTM7Owy0yuGJRe/wKt+gTfx6p/4Af6Hk2QPJrGgoajqprsrSKQw6Lrfztr6xubWdmGnuLu3f3BYOjpumjjVHBo8lrFuB8yAFAoaKFBCO9HAokBCKxjdTP3WI2gjYnWP4wT8iA2UCAVnaKVmdwRIn3qlsltxZ6CrxMtJmeSo90o/3X7M0wgUcsmM6Xhugn7GNAouYVLspgYSxkdsAB1LFYvA+Nns2gk9t0qfhrG2pZDO1L8TGYuMGUeB7YwYDs2yNxX/8zophlU/EypJERSfLwpTSTGm09dpX2jgKMeWMK6FvZXyIdOMow1oYUugmQ1mYnPxllNYJc3LiudWvLurcq2aJ1Qgp+SMXBCPXJMauSV10iCcPJAX8krenGfn3flwPueta04+c0IW4Hz9AvYZlzw=AAACAHicbVDLSgNBEJz1GeMr6tHLYBA8hV0RzDHgxWME84BkCbOT3mTM7Owy0yuGJRe/wKt+gTfx6p/4Af6Hk2QPJrGgoajqprsrSKQw6Lrfztr6xubWdmGnuLu3f3BYOjpumjjVHBo8lrFuB8yAFAoaKFBCO9HAokBCKxjdTP3WI2gjYnWP4wT8iA2UCAVnaKVmdwRIn3qlsltxZ6CrxMtJmeSo90o/3X7M0wgUcsmM6Xhugn7GNAouYVLspgYSxkdsAB1LFYvA+Nns2gk9t0qfhrG2pZDO1L8TGYuMGUeB7YwYDs2yNxX/8zophlU/EypJERSfLwpTSTGm09dpX2jgKMeWMK6FvZXyIdOMow1oYUugmQ1mYnPxllNYJc3LiudWvLurcq2aJ1Qgp+SMXBCPXJMauSV10iCcPJAX8krenGfn3flwPueta04+c0IW4Hz9AvYZlzw=AAACAHicbVDLSgNBEJz1GeMr6tHLYBA8hV0RzDHgxWME84BkCbOT3mTM7Owy0yuGJRe/wKt+gTfx6p/4Af6Hk2QPJrGgoajqprsrSKQw6Lrfztr6xubWdmGnuLu3f3BYOjpumjjVHBo8lrFuB8yAFAoaKFBCO9HAokBCKxjdTP3WI2gjYnWP4wT8iA2UCAVnaKVmdwRIn3qlsltxZ6CrxMtJmeSo90o/3X7M0wgUcsmM6Xhugn7GNAouYVLspgYSxkdsAB1LFYvA+Nns2gk9t0qfhrG2pZDO1L8TGYuMGUeB7YwYDs2yNxX/8zophlU/EypJERSfLwpTSTGm09dpX2jgKMeWMK6FvZXyIdOMow1oYUugmQ1mYnPxllNYJc3LiudWvLurcq2aJ1Qgp+SMXBCPXJMauSV10iCcPJAX8krenGfn3flwPueta04+c0IW4Hz9AvYZlzw=AAACAHicbVDLSgNBEJz1GeMr6tHLYBA8hV0RzDHgxWME84BkCbOT3mTM7Owy0yuGJRe/wKt+gTfx6p/4Af6Hk2QPJrGgoajqprsrSKQw6Lrfztr6xubWdmGnuLu3f3BYOjpumjjVHBo8lrFuB8yAFAoaKFBCO9HAokBCKxjdTP3WI2gjYnWP4wT8iA2UCAVnaKVmdwRIn3qlsltxZ6CrxMtJmeSo90o/3X7M0wgUcsmM6Xhugn7GNAouYVLspgYSxkdsAB1LFYvA+Nns2gk9t0qfhrG2pZDO1L8TGYuMGUeB7YwYDs2yNxX/8zophlU/EypJERSfLwpTSTGm09dpX2jgKMeWMK6FvZXyIdOMow1oYUugmQ1mYnPxllNYJc3LiudWvLurcq2aJ1Qgp+SMXBCPXJMauSV10iCcPJAX8krenGfn3flwPueta04+c0IW4Hz9AvYZlzw=

|0i
AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKez6wBwDXjxGMA9IljA76SRjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSyFQdf9dnJr6xubW/ntws7u3v5B8fCoYaJEc6jzSEa6FTADUiioo0AJrVgDCwMJzWB0O/WbT6CNiNQDjmPwQzZQoi84Qys1OiNA6naLJbfszkBXiZeREslQ6xZ/Or2IJyEo5JIZ0/bcGP2UaRRcwqTQSQzEjI/YANqWKhaC8dPZtRN6ZpUe7UfalkI6U/9OpCw0ZhwGtjNkODTL3lT8z2sn2K/4qVBxgqD4fFE/kRQjOn2d9oQGjnJsCeNa2FspHzLNONqAFrYEmtlgJjYXbzmFVdK4KHuX5ev7q1K1kiWUJyfklJwTj9yQKrkjNVInnDySF/JK3pxn5935cD7nrTknmzkmC3C+fgGF5Zb7

|f(x)i
AAACBHicbVDLTgJBEOzFF+IL9ehlIzHBC9n1ETmSePGIiYARCJkdZmHC7OxmptdINlz9Aq/6Bd6MV//DD/A/nIU9CFhJJ5Wq7nR3eZHgGh3n28qtrK6tb+Q3C1vbO7t7xf2Dpg5jRVmDhiJU9x7RTHDJGshRsPtIMRJ4grW80XXqtx6Z0jyUdziOWDcgA8l9Tgka6aEzYpj45afTSa9YcirOFPYycTNSggz1XvGn0w9pHDCJVBCt264TYTchCjkVbFLoxJpFhI7IgLUNlSRguptML57YJ0bp236oTEm0p+rfiYQEWo8Dz3QGBId60UvF/7x2jH61m3AZxcgknS3yY2FjaKfv232uGEUxNoRQxc2tNh0SRSiakOa2eIqYcNJc3MUUlknzrOKeVy5vL0q1apZQHo7gGMrgwhXU4Abq0AAKEl7gFd6sZ+vd+rA+Z605K5s5hDlYX78S8pj6

Imagine that we had written some routine/circuit to calculate some function, f.

On a classical computer, we can only evaluate the function for a single input, x, at a
time. What would happen if we input a superposition in a quantum computer?

MULT20015 Elements of Quantum Computing
Lecture 7

Quantum Parallelism

Uf
|0i

AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKez6wBwDXjxGMA9IljA76SRjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSyFQdf9dnJr6xubW/ntws7u3v5B8fCoYaJEc6jzSEa6FTADUiioo0AJrVgDCwMJzWB0O/WbT6CNiNQDjmPwQzZQoi84Qys1OiNA6naLJbfszkBXiZeREslQ6xZ/Or2IJyEo5JIZ0/bcGP2UaRRcwqTQSQzEjI/YANqWKhaC8dPZtRN6ZpUe7UfalkI6U/9OpCw0ZhwGtjNkODTL3lT8z2sn2K/4qVBxgqD4fFE/kRQjOn2d9oQGjnJsCeNa2FspHzLNONqAFrYEmtlgJjYXbzmFVdK4KHuX5ev7q1K1kiWUJyfklJwTj9yQKrkjNVInnDySF/JK3pxn5935cD7nrTknmzkmC3C+fgGF5Zb7

| i =
1

2n/2

2n�1X

x=0

|xi
AAACNnicbZDLSgMxFIYz9VbrrerSTbAIbqwzVbEIhYIblxXsBTptyaSZNjSTGZKMtIR5Fx/DJ3CrWzfuilsfwfSysK0/BH7+cw7n5PMiRqWy7U8rtba+sbmV3s7s7O7tH2QPj2oyjAUmVRyyUDQ8JAmjnFQVVYw0IkFQ4DFS9wb3k3r9mQhJQ/6kRhFpBajHqU8xUibqZO/cAVHQjSSFJej6AmHtJLrQ1vyykCTQlXHQ0cOSnbRNyOEFdExoRvQw6WRzdt6eCq4aZ25yYK5KJzt2uyGOA8IVZkjKpmNHqqWRUBQzkmTcWJII4QHqkaaxHAVEtvT0jwk8M0kX+qEwjys4Tf9OaBRIOQo80xkg1ZfLtUn4X60ZK7/Y0pRHsSIczxb5MYMqhBNgsEsFwYqNjEFYUHMrxH1kQCmDdWGLJ5AhM+HiLFNYNbVC3rnK3zxe58rFOaE0OAGn4Bw44BaUwQOogCrA4AW8gXfwYb1aX9bY+p61pqz5zDFYkPXzC1+Tq8g=

| 0i =
1

2n/2

2n�1X

x=0

|xi ⌦ |f(x)i
AAACS3icbZDLSgMxFIYz9X6vunQTLKIurDNV0U2h4MadClaFTi2ZNGNDM5khOSMtIY/lY/gA4lafwJ24ML0svB0I/PnP+TnJF2WCa/D9Z68wMTk1PTM7N7+wuLS8Ulxdu9Zpriir01Sk6jYimgkuWR04CHabKUaSSLCbqHs66N88MKV5Kq+gn7FmQu4ljzkl4KxW8TzsMsAmzDTftriKw1gRagJrKndG7lesxaHOk5bpVX1750yJ93DgTJcyPRumwBOmR9d4p7drW8WSX/aHhf+KYCxKaFwXreJb2E5pnjAJVBCtG4GfQdMQBZwKZufDXLOM0C65Zw0nJXH7mmb4cYu3nNPGcarckYCH7veEIYnW/SRykwmBjv7dG5j/9Ro5xCdNw2WWA5N0tCjOBYYUDyjiNleMgug7Qaji7q2YdohDB471jy2RIg7OgEvwm8JfcV0pBwflo8vDUu1kTGgWbaBNtIMCdIxq6AxdoDqi6BG9oFf05j15796H9zkaLXjjzDr6UYWpLxxts44=

An equal superposition
of inputs

The function evaluates all the inputs in superposition with just one application of
Uf .

H⊗n|0i
AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKez6wBwDXjxGMA9IljA76SRjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSyFQdf9dnJr6xubW/ntws7u3v5B8fCoYaJEc6jzSEa6FTADUiioo0AJrVgDCwMJzWB0O/WbT6CNiNQDjmPwQzZQoi84Qys1OiNA6naLJbfszkBXiZeREslQ6xZ/Or2IJyEo5JIZ0/bcGP2UaRRcwqTQSQzEjI/YANqWKhaC8dPZtRN6ZpUe7UfalkI6U/9OpCw0ZhwGtjNkODTL3lT8z2sn2K/4qVBxgqD4fFE/kRQjOn2d9oQGjnJsCeNa2FspHzLNONqAFrYEmtlgJjYXbzmFVdK4KHuX5ev7q1K1kiWUJyfklJwTj9yQKrkjNVInnDySF/JK3pxn5935cD7nrTknmzkmC3C+fgGF5Zb7

MULT20015 Elements of Quantum Computing
Lecture 7

Quantum Parallelism Example

x f(x)

0 0

1 1

2 4

3 9

4 16

5 25

6 36

7 49

f(x) = x2
AAACBHicbVDLTgJBEJz1ifhCPXqZSEzwQnZRIxcTEi8eMZFHhJXMDr0wYXZ2MzNrIBuufoFX/QJvxqv/4Qf4Hw6wBwEr6aRS1Z3uLi/iTGnb/rZWVtfWNzYzW9ntnd29/dzBYV2FsaRQoyEPZdMjCjgTUNNMc2hGEkjgcWh4g5uJ33gCqVgo7vUoAjcgPcF8Rok20oNfGJ7hazx8LHVyebtoT4GXiZOSPEpR7eR+2t2QxgEITTlRquXYkXYTIjWjHMbZdqwgInRAetAyVJAAlJtMLx7jU6N0sR9KU0Ljqfp3IiGBUqPAM50B0X216E3E/7xWrP2ymzARxRoEnS3yY451iCfv4y6TQDUfGUKoZOZWTPtEEqpNSHNbPEkGoMcmF2cxhWVSLxWd8+Ll3UW+Uk4TyqBjdIIKyEFXqIJuURXVEEUCvaBX9GY9W+/Wh/U5a12x0pkjNAfr6xdYVpfn

Uf
|0i

| i =
1

2n/2

2n�1X

x=0

| 0i =
1

2n/2

2n�1X

x=0

Consider evaluating the function:

The output also is a superposition, evaluated for each input:

“Quantum parallelism” – evaluated on entire superposition in one application of the function.

| 0i =
|0i |0i+ |1i |1i+ |2i |4i+ |3i |9i+ |4i |16i+ |5i |25i+ |6i |36i+ |7i |49i

2
p
2

AAACpXicbZHbSgMxEIaz66nWQ6teehMsUkEouz1pLzyAN94ICm0VuqVk06yGZg8mWaEseSAfyQfwPUx316qtAyE/38xkwj9uxKiQlvVhmCura+sbhc3i1vbObqm8t98XYcwx6eGQhfzJRYIwGpCepJKRp4gT5LuMPLqTm1n+8Y1wQcOgK6cRGfroOaAexUhqNCq/OxMiEycStKrgheNxhJMUWSq/4ClMla3y6xvUM9Ccg0YGOnPQzFvac9LKSL01J+2MNH5qzvJ3O0oldUe88tkoVRyVK1bNSgMuCzsXFZDH/aj86YxDHPskkJghIQa2FclhgrikmBFVdGJBIoQn6JkMtAyQT8QwSS1V8FiTMfRCrk8gYUp/dyTIF2Lqu7rSR/JFLOZm8L/cIJbe+TChQRRLEuBskBczKEM42w8cU06wZFMtEOZU/xXiF6TXIvUW/0xxOdI+Ke2LvejCsujXa3aj1npoVq7Pc4cK4BAcgRNggzNwDW7BPegBbJSMlnFpXJlV887smv2s1DTyngPwJ8zRFz2Lz1Y=

MULT20015 Elements of Quantum Computing
Lecture 7

7.5 Multiqubit Measurement

MULT20015
Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7

Recap: Two-qubit measurement

Measurement on a two-qubit state:
1) Apply collapse principle to the measured state
2) Renormalize the state probabilities

For example, consider the
general two-qubit state:

If the first qubit were measured to be “0”, keep
only those states and renormalize to get the
new state:

| i = a |00i+ b |01i+ c |10i+ d |11i
AAACNXicbZDLSgMxFIYzXmu9jbp0EyyCIJSMCFZBKLhxWcGxhc5QMpm0Dc1cSDJCGeZdfAyfwK1u3bhSt76CmcvCtv4Q+PKfczjJ78WcSYXQu7G0vLK6tl7bqG9ube/smnv7DzJKBKE2iXgkeh6WlLOQ2oopTnuxoDjwOO16k5u83n2kQrIovFfTmLoBHoVsyAhW2hqYV86EqtSJJcvgNcTFDaEMnkKvZCtnUrBV+H7JVjYwG6iJCsFFsCpogEqdgfnl+BFJAhoqwrGUfQvFyk2xUIxwmtWdRNIYkwke0b7GEAdUumnxxwwea8eHw0joEypYuH8nUhxIOQ083RlgNZbztdz8r9ZP1LDlpiyME0VDUi4aJhyqCOaBQZ8JShSfasBEMP1WSMZYYKJ0rDNbPIF1NHku1nwKi2CfNS+b6O680W5VAdXAITgCJ8ACF6ANbkEH2ICAJ/ACXsGb8Wx8GJ/Gd9m6ZFQzB2BGxs8v5lqqfA==AAACNXicbZDLSgMxFIYzXmu9jbp0EyyCIJSMCFZBKLhxWcGxhc5QMpm0Dc1cSDJCGeZdfAyfwK1u3bhSt76CmcvCtv4Q+PKfczjJ78WcSYXQu7G0vLK6tl7bqG9ube/smnv7DzJKBKE2iXgkeh6WlLOQ2oopTnuxoDjwOO16k5u83n2kQrIovFfTmLoBHoVsyAhW2hqYV86EqtSJJcvgNcTFDaEMnkKvZCtnUrBV+H7JVjYwG6iJCsFFsCpogEqdgfnl+BFJAhoqwrGUfQvFyk2xUIxwmtWdRNIYkwke0b7GEAdUumnxxwwea8eHw0joEypYuH8nUhxIOQ083RlgNZbztdz8r9ZP1LDlpiyME0VDUi4aJhyqCOaBQZ8JShSfasBEMP1WSMZYYKJ0rDNbPIF1NHku1nwKi2CfNS+b6O680W5VAdXAITgCJ8ACF6ANbkEH2ICAJ/ACXsGb8Wx8GJ/Gd9m6ZFQzB2BGxs8v5lqqfA==AAACNXicbZDLSgMxFIYzXmu9jbp0EyyCIJSMCFZBKLhxWcGxhc5QMpm0Dc1cSDJCGeZdfAyfwK1u3bhSt76CmcvCtv4Q+PKfczjJ78WcSYXQu7G0vLK6tl7bqG9ube/smnv7DzJKBKE2iXgkeh6WlLOQ2oopTnuxoDjwOO16k5u83n2kQrIovFfTmLoBHoVsyAhW2hqYV86EqtSJJcvgNcTFDaEMnkKvZCtnUrBV+H7JVjYwG6iJCsFFsCpogEqdgfnl+BFJAhoqwrGUfQvFyk2xUIxwmtWdRNIYkwke0b7GEAdUumnxxwwea8eHw0joEypYuH8nUhxIOQ083RlgNZbztdz8r9ZP1LDlpiyME0VDUi4aJhyqCOaBQZ8JShSfasBEMP1WSMZYYKJ0rDNbPIF1NHku1nwKi2CfNS+b6O680W5VAdXAITgCJ8ACF6ANbkEH2ICAJ/ACXsGb8Wx8GJ/Gd9m6ZFQzB2BGxs8v5lqqfA==

| 0i =
a |00i+ b |01i
p

|a|2 + |b|2
AAACO3icbZDLSgMxFIYz9X6vunQTLKIglJkiqAuh4MZlBWuFTi1n0kwbmrmYnBHKdF7Hx/AJ3Cq41424dW96WdjWAyE//38OJ/m8WAqNtv1u5ebmFxaXlldW19Y3Nrfy2zu3OkoU41UWyUjdeaC5FCGvokDJ72LFIfAkr3ndy0Fee+RKiyi8wV7MGwG0Q+ELBmisZr7sdjmmbqzFYUYvqOsrYCkMTdvO6DH1RtrJstTVDwrTPvTvSyboe+bOsma+YBftYdFZ4YxFgYyr0sx/uq2IJQEPkUnQuu7YMTZSUCiY5Nmqm2geA+tCm9eNDCHgupEOf5rRA+O0qB8pc0KkQ/fvRAqB1r3AM50BYEdPZwPzv6yeoH/WSEUYJ8hDNlrkJ5JiRAfYaEsozlD2jACmhHkrZR0wsNDAndjiKTDEBlycaQqzoloqnhft65NC+WwMaJnskX1yRBxySsrkilRIlTDyRF7IK3mznq0P68v6HrXmrPHMLpko6+cXiDCukw==AAACO3icbZDLSgMxFIYz9X6vunQTLKIglJkiqAuh4MZlBWuFTi1n0kwbmrmYnBHKdF7Hx/AJ3Cq41424dW96WdjWAyE//38OJ/m8WAqNtv1u5ebmFxaXlldW19Y3Nrfy2zu3OkoU41UWyUjdeaC5FCGvokDJ72LFIfAkr3ndy0Fee+RKiyi8wV7MGwG0Q+ELBmisZr7sdjmmbqzFYUYvqOsrYCkMTdvO6DH1RtrJstTVDwrTPvTvSyboe+bOsma+YBftYdFZ4YxFgYyr0sx/uq2IJQEPkUnQuu7YMTZSUCiY5Nmqm2geA+tCm9eNDCHgupEOf5rRA+O0qB8pc0KkQ/fvRAqB1r3AM50BYEdPZwPzv6yeoH/WSEUYJ8hDNlrkJ5JiRAfYaEsozlD2jACmhHkrZR0wsNDAndjiKTDEBlycaQqzoloqnhft65NC+WwMaJnskX1yRBxySsrkilRIlTDyRF7IK3mznq0P68v6HrXmrPHMLpko6+cXiDCukw==AAACO3icbZDLSgMxFIYz9X6vunQTLKIglJkiqAuh4MZlBWuFTi1n0kwbmrmYnBHKdF7Hx/AJ3Cq41424dW96WdjWAyE//38OJ/m8WAqNtv1u5ebmFxaXlldW19Y3Nrfy2zu3OkoU41UWyUjdeaC5FCGvokDJ72LFIfAkr3ndy0Fee+RKiyi8wV7MGwG0Q+ELBmisZr7sdjmmbqzFYUYvqOsrYCkMTdvO6DH1RtrJstTVDwrTPvTvSyboe+bOsma+YBftYdFZ4YxFgYyr0sx/uq2IJQEPkUnQuu7YMTZSUCiY5Nmqm2geA+tCm9eNDCHgupEOf5rRA+O0qB8pc0KkQ/fvRAqB1r3AM50BYEdPZwPzv6yeoH/WSEUYJ8hDNlrkJ5JiRAfYaEsozlD2jACmhHkrZR0wsNDAndjiKTDEBlycaQqzoloqnhft65NC+WwMaJnskX1yRBxySsrkilRIlTDyRF7IK3mznq0P68v6HrXmrPHMLpko6+cXiDCukw==

normalization
If the first qubit were measured to be “1”, keep
only those states and renormalize to get the
new state:

| 0i =
c |10i+ d |11i
p

|c|2 + |d|2

MULT20015 Elements of Quantum Computing
Lecture 7

Multi-qubit measurement

Measurement on a multi-qubit state:
1) Apply collapse principle to the measured state – keep only the

amplitudes compatible with the measurement.
2) Renormalize the state probabilities, so the probabilities sum to 1.

| i =
1

2
|1i |5i+

2
|1i |6i+

1
p
2
|3i |8i

For example, consider the state:

Imagine that we measured the first register. There are two possible outcomes:
“1” and “3”. What are the probabilities?

|xi |yi
AAACB3icbZBLSgNBEIZrfMb4irp00xgEV2HGB2YZcOMygnlAMoSeTk/SpOdhd40YhhzAE7jVE7gTtx7DA3gPO5NZmMSCpn/+v4oqPi+WQqNtf1srq2vrG5uFreL2zu7efungsKmjRDHeYJGMVNujmksR8gYKlLwdK04DT/KWN7qZ5q1HrrSIwnscx9wN6CAUvmAUjeV2RxzJE8m+ca9Utit2VmRZOLkoQ171Xumn249YEvAQmaRadxw7RjelCgWTfFLsJprHlI3ogHeMDGnAtZtmR0/IqXH6xI+UeSGSzP07kdJA63Hgmc6A4lAvZlPzv6yToF91UxHGCfKQzRb5iSQYkSkB0heKM5RjIyhTwtxK2JAqytBwmtviKWrATAwXZ5HCsmieV5yLytXdZblWzQkV4BhO4AwcuIYa3EIdGsDgAV7gFd6sZ+vd+rA+Z60rVj5zBHNlff0CzU+Z4g==

Note: multiple
qubits in each
register

|xi
AAACAHicbVDLSgNBEJz1GeMr6tHLYBA8hV0fmGPAi8cI5gHJEmYnnWTM7Owy0yuGJRe/wKt+gTfx6p/4Af6Hk2QPJrGgoajqprsriKUw6Lrfzsrq2vrGZm4rv72zu7dfODismyjRHGo8kpFuBsyAFApqKFBCM9bAwkBCIxjeTPzGI2gjInWPoxj8kPWV6AnO0Er19hCQPnUKRbfkTkGXiZeRIslQ7RR+2t2IJyEo5JIZ0/LcGP2UaRRcwjjfTgzEjA9ZH1qWKhaC8dPptWN6apUu7UXalkI6Vf9OpCw0ZhQGtjNkODCL3kT8z2sl2Cv7qVBxgqD4bFEvkRQjOnmddoUGjnJkCeNa2FspHzDNONqA5rYEmtlgxjYXbzGFZVI/L3kXpau7y2KlnCWUI8fkhJwRj1yTCrklVVIjnDyQF/JK3pxn5935cD5nrStONnNE5uB8/QL4XZdD

MULT20015 Elements of Quantum Computing
Lecture 7

Multi-qubit measurement

| i =
1

2
|1i |5i+

2
|1i |6i+

1
p
2
|3i |8i

Probability of
measuring “1”: P1 =

✓
1

◆2
+

✓
1

◆2

=
1

2AAACdnichVFNSyNBEO0ZP1az7jrqUZBmgx+7QpiJLHoRBC8eIxgVMjHUdGqSJj09s901C3HID/XmZf/DHu3EgF8LW9DweK+qXvE6KZS0FIYPnr+wuLT8aWW19nnty9f1YGPz2ualEdgWucrNbQIWldTYJkkKbwuDkCUKb5LR+VS/+Y3Gylxf0bjAbgYDLVMpgBzVC+7jBAdSV/hLgzEw/jGptXoR3zvd47HClA54nBoQVTSpmhMeGzkY0nd+1+SH/9HjuDZb8qLWYtT9V0a9oB42wlnxjyCagzqbV6sX/In7uSgz1CQUWNuJwoK6FRiSQqHbX1osQIxggB0HNWRou9UsownfdUyfp7lxTxOfsa8nKsisHWeJ68yAhva9NiX/pXVKSk+6ldRFSajFs1FaKk45nwbO+9KgIDV2AISR7lYuhuBSIfctb1wSAyOkaS7R+xQ+gutmIzpq/Lxs1s9O5gmtsG32jR2wiB2zM3bBWqzNBHv0lr11L/D++jv+rr//3Op785kt9qb88AkDYLvf

Probability of measuring “3”:
P3 =

✓
1
p
2

◆2

=
1

2AAACXHicbZDPSxtBFMcnW1s11hor9NLL0FCxPYTdFdFLQfDiMUKjQiZN307eJkNmZ9eZt4Ww7L/n/+Clt956redOYgR/PRj48n3f997wSQqtHIXhTSN4tfL6zeraenPj7ea7rdb2+3OXl1ZiT+Y6t5cJONTKYI8UabwsLEKWaLxIpifz/sUvtE7l5jvNChxkMDYqVRLIW8PWT5HgWJkKrwxYC7OvdbM73Oe733a50JjSHhepBVlFdSXclaUqrmsurBpP6MuPmAvRXETvM3HdFGhGD9YNW+2wEy6KPxfRUrTZsrrD1h8xymWZoSGpwbl+FBY0qMCSkhr9/tJhAXIKY+x7aSBDN6gWJGr+2TsjnubWP0N84T6cqCBzbpYlPpkBTdzT3tx8qdcvKT0aVMoUJaGRd4fSUnPK+RwrHymLkvTMC5BW+b9yOQFPhTz8R1cSC1OkOZfoKYXn4jzuRPudg7O4fXy0JLTGPrJPbI9F7JAds1PWZT0m2TX7y/6x28bvYCXYCDbvokFjObPDHlXw4T9SBrZg

MULT20015 Elements of Quantum Computing
Lecture 7

Multi-qubit measurement

| i =
1

2
|1i |5i+

2
|1i |6i+

1
p
2
|3i |8i

If the measurement outcome “1” were measured, the (unnormalized) state
compatible with this is:

After normalization, the state becomes:

2
|1i |5i+

2
|1i |6i

AAACM3icdZDLSsNAFIYn9VbrLerSzWARBKEk1douC25cVrAXaEqZTCft0MkkzEyEEvIoPoZP4FYfQNyJLn0HJ2kWttUDw/z8/zmcmc8NGZXKst6Mwtr6xuZWcbu0s7u3f2AeHnVkEAlM2jhggei5SBJGOWkrqhjphYIg32Wk605v0rz7QISkAb9Xs5AMfDTm1KMYKW0NzbrjCYRjO4mrCXSmRGmZXbUEXsD/wutkaJatipUVXBV2Lsogr9bQ/HJGAY58whVmSMq+bYVqECOhKGYkKTmRJCHCUzQmfS058okcxNkHE3imnRH0AqEPVzBzf0/EyJdy5ru600dqIpez1Pwr60fKawxiysNIEY7ni7yIQRXAlBYcUUGwYjMtEBZUvxXiCdJQlGa6sMUVSJNJudjLFFZFp1qxLyu1u6tys5ETKoITcArOgQ3qoAluQQu0AQaP4Bm8gFfjyXg3PozPeWvByGeOwUIZ3z+rHauU

| 0i =
1
2
|1i |5i+ 1

2
|1i |6i

q
1
2

2
+ 1

AAACbXicdZHLSgMxFIYzo9Zab1VxpUiwSAWhzNRbN4LgxqWCVaHTlkyaqaGZi8kZoYR5TvEBXPsEgpm2i7bqgSQ//38OCV/8RHAFjvNh2QuLS4Xl4kppdW19Y7O8tf2o4lRS1qSxiOWzTxQTPGJN4CDYcyIZCX3BnvzBTZ4/vTGpeBw9wDBh7ZD0Ix5wSsBY3fKrN2CgvUTxaoavsBdIQvV4dzNdz3CeY3d8nOMT/F92kWlPvUrQ0x2d+uxEp55l3XLFqTmjwr+FOxEVNKm7bvnT68U0DVkEVBClWq6TQFsTCZwKlpW8VLGE0AHps5aREQmZausRmgwfGaeHg1iaFQEeudMTmoRKDUPfdIYEXtR8lpt/Za0UgkZb8yhJgUV0fFGQCgwxzjnjHpeMghgaQajk5q2YvhBDAsxvzNziS2IA5lzceQq/xWO95p7Wzu/PKteNCaEi2kOH6Bi56BJdo1t0h5qIonf0bRWsZevL3rX37YNxq21NZnbQTNnVHz5Ouuk=

| 0i =
|1i |5i+ |1i |6i

p
2

AAACOnicbZDLSgMxFIYzXmu9jbp0EyyiIJSZarUbpeDGZQVbhU4pmTSjoZmLyRmhDHkbH8MncKsbt4ILcesDmE5n4e1AyM//n8NJPj8RXIHjvFhT0zOzc/OlhfLi0vLKqr223lFxKilr01jE8sonigkesTZwEOwqkYyEvmCX/vB0nF/eMal4HF3AKGG9kFxHPOCUgLH69ok3ZJB5ieI7Gh9jL5CEZrnn6vyqa7yHvxuHWmeeupWQ1bTu2xWn6uSF/wq3EBVUVKtvv3mDmKYhi4AKolTXdRLoZUQCp4LpspcqlhA6JNesa2REQqZ6Wf5PjbeNM8BBLM2JAOfu94mMhEqNQt90hgRu1O9sbP6XdVMIGr2MR0kKLKKTRUEqMMR4DA0PuGQUxMgIQiU3b8X0hhhUYND+2OJLYiCNubi/KfwVnVrV3a/Wzw8qzUZBqIQ20RbaRS46Qk10hlqojSi6R4/oCT1bD9ar9W59TFqnrGJmA/0o6/MLgnOvIA==

MULT20015 Elements of Quantum Computing
Lecture 7

Multi-qubit measurement

| i =
1

2
|1i |5i+

2
|1i |6i+

1
p
2
|3i |8i

If the measurement outcome “3” were measured, the (unnormalized) state
compatible with this is:

After normalization, the state becomes:

1
p
2
|3i |8i

AAACHXicbZDLSgMxFIYz9VbrbdSlm2gRXJWZVrHLghuXFewFOkPJpJk2NHMxOSOUYdY+hk/gVp/AnbgVH8D3MJ12YVsPhPz8/zmc5PNiwRVY1rdRWFvf2Nwqbpd2dvf2D8zDo7aKEklZi0Yikl2PKCZ4yFrAQbBuLBkJPME63vhmmncemVQ8Cu9hEjM3IMOQ+5wS0FbfPHV8SWhqZ6mjHiSk1SzDzphBWsvyq571zbJVsfLCq8KeizKaV7Nv/jiDiCYBC4EKolTPtmJwUyKBU8GykpMoFhM6JkPW0zIkAVNumn8lw+faGWA/kvqEgHP370RKAqUmgac7AwIjtZxNzf+yXgJ+3U15GCfAQjpb5CcCQ4SnXPCAS0ZBTLQgVHL9VkxHRLMBTW9hiyeJJjPlYi9TWBXtasWuVa7uLsuN+pxQEZ2gM3SBbHSNGugWNVELUfSEXtArejOejXfjw/ictRaM+cwxWijj6xeKB6Nu

| 0i =
1p
2
|3i |8i

r⇣
1p
2

⌘2
AAACW3icbZBLSwMxFIXT8V1fVXHlJljEuikzVbEbQXDjUsE+oFNLJr3ThmYeJneEMszP80e4cOnKre7NtBWseiHJ4dxzueHzYik02vZLwVpYXFpeWV0rrm9sbm2XdnabOkoUhwaPZKTaHtMgRQgNFCihHStggSeh5Y2u837rCZQWUXiP4xi6ARuEwhecobF6pZ47AkzdWIvjjF5S11eMp9PbyVJXPypMa1lG8xg9nT7174YrwcfKfJrWMleJwRBPHvK5XqlsV+1J0b/CmYkymdVtr/Tm9iOeBBAil0zrjmPH2E2ZQsElZEU30RAzPmID6BgZsgB0N52AyOiRcfrUj5Q5IdKJ+3MiZYHW48AzyYDhUP/u5eZ/vU6Cfr2bijBOEEI+XeQnkmJEc6q0LxRwlGMjGFfC/JXyITNc0LCf2+IpZhhmhovzm8Jf0axVndPq+d1Z+ao+I7RKDsghqRCHXJArckNuSYNw8kzeyQf5LLxaC1bR2phGrcJsZo/MlbX/BZ+huEs=

| 0i = |3i |8i
AAACF3icbVDLSgMxFM3UV62vUZfdBIvoqsxYxW6EghuXFewDOkPJpGkbmnmQ3BHKMAs/wy9wq1/gTty69AP8DzPtLGzrgZCTc+7l3hwvElyBZX0bhbX1jc2t4nZpZ3dv/8A8PGqrMJaUtWgoQtn1iGKCB6wFHATrRpIR3xOs401uM7/zyKTiYfAA04i5PhkFfMgpAS31zbIzYZA4keJnKb7B2QvX5le9b1asqjUDXiV2TiooR7Nv/jiDkMY+C4AKolTPtiJwEyKBU8HSkhMrFhE6ISPW0zQgPlNuMvtEik+1MsDDUOoTAJ6pfzsS4is19T1d6RMYq2UvE//zejEM627CgygGFtD5oGEsMIQ4SwQPuGQUxFQTQiXXu2I6JpJQ0LktTPEk0cGkOhd7OYVV0r6o2rXq1f1lpVHPEyqiMjpB58hG16iB7lATtRBFT+gFvaI349l4Nz6Mz3lpwch7jtECjK9fpCee/Q==

MULT20015 Elements of Quantum Computing
Lecture 7

7.6 The Toffoli Gate

MULT20015
Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7

Toffoli gate

Control qubit

Target qubit

Toffoli gate plus NOT is universal for classical computation. It was used in the
proof that classical computation can be made reversible!

How states transform:

Rule: the target is flipped
iff both the control qubits
are in “1” state.

Control qubit

|000i ! |000i
|001i ! |001i
|010i ! |010i
|011i ! |011i
|100i ! |100i
|101i ! |101i
|110i ! |111i
|111i ! |110i

a |000i+ b |001i+ c |010i+ d |011i
e |100i+ f |101i+ g |110i+ h |111i
! a |000i+ b |001i+ c |010i+ d |011i

e |100i+ f |101i+ h |110i+ g |111i
AAAC73icnVLNihQxEE63f+v4N+rRS3BwEYQhWQT3uODF4wrO7sr0MFSnq7vDpH82qVaGZvCqT+BNvPpIPoBP4AuY6W5lf8SDFQLfV199VFFJXBvtSIjvQXjl6rXrN3Zujm7dvnP33vj+gyNXNVbhTFWmsicxODS6xBlpMnhSW4QiNngcr15u9eN3aJ2uyje0rnFRQFbqVCsgn1qOf+5y4NEKqRVCbPgzHg9EbonqieyUZCBeiaLRLsfeJ3tfOpDOl/Wk9+UD+e2LrM5yAmur9//dOzptIOGRP/+YIj87RfZnitFyPBFT0QW/DOQAJmyIw+X4R5RUqimwJGXAubkUNS1asKSVwc0oahzWoFaQ4dzDEgp0i7Z7nA1/4jMJTyvrb0m8y551tFA4ty5iX1kA5e6itk3+TZs3lO4vWl3WDWGp+kZpYzhVfPvSPNEWFZm1B6Cs9rNylYMFRf4/nOsSW/DL2fi9yItbuAyO9qZSTOXr55OD/WFDO+wRe8yeMslesAP2ih2yGVPB2+BD8DH4FJ6Gn8Mv4de+NAwGz0N2LsJvvwCPAN+QAAAC73icnVLNihQxEE63f+v4N+rRS3BwEYQhWQT3uODF4wrO7sr0MFSnq7vDpH82qVaGZvCqT+BNvPpIPoBP4AuY6W5lf8SDFQLfV199VFFJXBvtSIjvQXjl6rXrN3Zujm7dvnP33vj+gyNXNVbhTFWmsicxODS6xBlpMnhSW4QiNngcr15u9eN3aJ2uyje0rnFRQFbqVCsgn1qOf+5y4NEKqRVCbPgzHg9EbonqieyUZCBeiaLRLsfeJ3tfOpDOl/Wk9+UD+e2LrM5yAmur9//dOzptIOGRP/+YIj87RfZnitFyPBFT0QW/DOQAJmyIw+X4R5RUqimwJGXAubkUNS1asKSVwc0oahzWoFaQ4dzDEgp0i7Z7nA1/4jMJTyvrb0m8y551tFA4ty5iX1kA5e6itk3+TZs3lO4vWl3WDWGp+kZpYzhVfPvSPNEWFZm1B6Cs9rNylYMFRf4/nOsSW/DL2fi9yItbuAyO9qZSTOXr55OD/WFDO+wRe8yeMslesAP2ih2yGVPB2+BD8DH4FJ6Gn8Mv4de+NAwGz0N2LsJvvwCPAN+QAAAC73icnVLNihQxEE63f+v4N+rRS3BwEYQhWQT3uODF4wrO7sr0MFSnq7vDpH82qVaGZvCqT+BNvPpIPoBP4AuY6W5lf8SDFQLfV199VFFJXBvtSIjvQXjl6rXrN3Zujm7dvnP33vj+gyNXNVbhTFWmsicxODS6xBlpMnhSW4QiNngcr15u9eN3aJ2uyje0rnFRQFbqVCsgn1qOf+5y4NEKqRVCbPgzHg9EbonqieyUZCBeiaLRLsfeJ3tfOpDOl/Wk9+UD+e2LrM5yAmur9//dOzptIOGRP/+YIj87RfZnitFyPBFT0QW/DOQAJmyIw+X4R5RUqimwJGXAubkUNS1asKSVwc0oahzWoFaQ4dzDEgp0i7Z7nA1/4jMJTyvrb0m8y551tFA4ty5iX1kA5e6itk3+TZs3lO4vWl3WDWGp+kZpYzhVfPvSPNEWFZm1B6Cs9rNylYMFRf4/nOsSW/DL2fi9yItbuAyO9qZSTOXr55OD/WFDO+wRe8yeMslesAP2ih2yGVPB2+BD8DH4FJ6Gn8Mv4de+NAwGz0N2LsJvvwCPAN+QAAAC73icnVLNihQxEE63f+v4N+rRS3BwEYQhWQT3uODF4wrO7sr0MFSnq7vDpH82qVaGZvCqT+BNvPpIPoBP4AuY6W5lf8SDFQLfV199VFFJXBvtSIjvQXjl6rXrN3Zujm7dvnP33vj+gyNXNVbhTFWmsicxODS6xBlpMnhSW4QiNngcr15u9eN3aJ2uyje0rnFRQFbqVCsgn1qOf+5y4NEKqRVCbPgzHg9EbonqieyUZCBeiaLRLsfeJ3tfOpDOl/Wk9+UD+e2LrM5yAmur9//dOzptIOGRP/+YIj87RfZnitFyPBFT0QW/DOQAJmyIw+X4R5RUqimwJGXAubkUNS1asKSVwc0oahzWoFaQ4dzDEgp0i7Z7nA1/4jMJTyvrb0m8y551tFA4ty5iX1kA5e6itk3+TZs3lO4vWl3WDWGp+kZpYzhVfPvSPNEWFZm1B6Cs9rNylYMFRf4/nOsSW/DL2fi9yItbuAyO9qZSTOXr55OD/WFDO+wRe8yeMslesAP2ih2yGVPB2+BD8DH4FJ6Gn8Mv4de+NAwGz0N2LsJvvwCPAN+Q

MULT20015 Elements of Quantum Computing
Lecture 7

Toffoli Gate

|ai
AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKez6wBwDXjxGMA9IljA76SRjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSy4Nq777eTW1jc2t/LbhZ3dvf2D4uFRQ0eJYlhnkYhUK6AaBZdYN9wIbMUKaRgIbAaj26nffEKleSQfzDhGP6QDyfucUWOlRmeEhtBuseSW3RnIKvEyUoIMtW7xp9OLWBKiNExQrdueGxs/pcpwJnBS6CQaY8pGdIBtSyUNUfvp7NoJObNKj/QjZUsaMlP/TqQ01HocBrYzpGaol72p+J/XTky/4qdcxolByeaL+okgJiLT10mPK2RGjC2hTHF7K2FDqigzNqCFLYGiNpiJzcVbTmGVNC7K3mX5+v6qVK1kCeXhBE7hHDy4gSrcQQ3qwOARXuAV3pxn5935cD7nrTknmzmGBThfv9PMlyw=

|bi
AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKez6wBwDXjxGMA9IljA76SRjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSyFQdf9dnJr6xubW/ntws7u3v5B8fCoYaJEc6jzSEa6FTADUiioo0AJrVgDCwMJzWB0O/WbT6CNiNQDjmPwQzZQoi84Qys1OiNAGnSLJbfszkBXiZeREslQ6xZ/Or2IJyEo5JIZ0/bcGP2UaRRcwqTQSQzEjI/YANqWKhaC8dPZtRN6ZpUe7UfalkI6U/9OpCw0ZhwGtjNkODTL3lT8z2sn2K/4qVBxgqD4fFE/kRQjOn2d9oQGjnJsCeNa2FspHzLNONqAFrYEmtlgJjYXbzmFVdK4KHuX5ev7q1K1kiWUJyfklJwTj9yQKrkjNVInnDySF/JK3pxn5935cD7nrTknmzkmC3C+fgHVY5ct

|ci
AAACAHicbVDJSgNBFHwTtxi3qEcvjUHwFGZcMMeAF48RzALJEHo6b5I2PQvdPUIYcvELvOoXeBOv/okf4H/Yk8zBJBY0FFXvUa/LiwVX2ra/rcLa+sbmVnG7tLO7t39QPjxqqSiRDJssEpHseFSh4CE2NdcCO7FEGngC2974NvPbTygVj8IHPYnRDegw5D5nVBup1RujJqxfrthVewaySpycVCBHo1/+6Q0ilgQYaiaoUl3HjrWbUqk5Ezgt9RKFMWVjOsSuoSENULnp7NopOTPKgPiRNC806Zn6dyOlgVKTwDOTAdUjtexl4n9eN9F+zU15GCcaQzYP8hNBdESyr5MBl8i0mBhCmeTmVsJGVFKmTUELKZ6kppip6cVZbmGVtC6qzmX1+v6qUq/lDRXhBE7hHBy4gTrcQQOawOARXuAV3qxn6936sD7nowUr3zmGBVhfv9b6ly4=

|c0i
AAACAnicbVDJSgNBEK2JW4xb1KOXxiB6CjMumGPAi8cIZoFkCD2dnqRJz0J3jRCG3PwCr/oF3sSrP+IH+B/2JHMwiQ8KHu9VUVXPi6XQaNvfVmFtfWNzq7hd2tnd2z8oHx61dJQoxpsskpHqeFRzKULeRIGSd2LFaeBJ3vbGd5nffuJKiyh8xEnM3YAOQ+ELRtFInd6YY8rOp/1yxa7aM5BV4uSkAjka/fJPbxCxJOAhMkm17jp2jG5KFQom+bTUSzSPKRvTIe8aGtKAazed3TslZ0YZED9SpkIkM/XvREoDrSeBZzoDiiO97GXif143Qb/mpiKME+Qhmy/yE0kwItnzZCAUZygnhlCmhLmVsBFVlKGJaGGLp6iJJsvFWU5hlbQuq85V9ebhulKv5QkV4QRO4QIcuIU63EMDmsBAwgu8wpv1bL1bH9bnvLVg5TPHsADr6xe8A5hB

Toffoli gate

Control-Control-NOT gate

a b c c’

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

MULT20015 Elements of Quantum Computing
Lecture 7

Multiply Controlled operations in QUI

You can add controls on single
qubit gates in QUI.

Right click on a gate and select
“Add Control on 1”

Click on the qubit where you would like a
control. Repeat for as many controls as you
would like.

MULT20015 Elements of Quantum Computing
Lecture 7

Week 4

Lecture 7
7.1 Binary notation with multiple qubits
7.2 Quantum Registers
7.3 Hadamard gates and equal superposition
7.4 Quantum “Parallelism”
7.5 Multiqubit measurement
7.6 Toffoli gate

Lecture 8
8.1 Classical digital logic and universality
8.2 Reversible logic
8.3 Arithmetic operations on a quantum computer
8.4 Universality in quantum computing

Practice class 4
Multi-qubit states and operations

MULT20015 Elements of Quantum Computing
Lecture 7

Subject outline

Lecture topics (by week)

Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8

Related Posts