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

MULT20015 Elements of Quantum Computing
Lecture 8

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 8

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 8

Recap: Lecture 7

|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=

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

Quantum Registers: Group qubits together

H⊗n|0i

Hadamard gates: Create an equal
superposition state at the start of the
algorithm

| i =
1

2n/2

2n�1X

i=0

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

|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: Doubly controlled NOT gate

| 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==

Multiqubit measurement: Apply the
collapse principle, and renormalize the
state.

MULT20015 Elements of Quantum Computing
Lecture 8

8.1 Classical Logic and Universality

MULT20015
Lecture 8

MULT20015 Elements of Quantum Computing
Lecture 8

AND Gate

An example of a classical digital logic operation is the AND gate:

A B A B

0 0 0

0 1 0

1 0 0

1 1 1

Output

B
AB

Inputs

MULT20015 Elements of Quantum Computing
Lecture 8

OR Gate

Another example is the OR gate:

A B A OR B

0 0 0

0 1 1

1 0 1

1 1 1

OutputInputs

B
A OR B

MULT20015 Elements of Quantum Computing
Lecture 8

NOT Gate

Our final example of a digital logic gate:

A NOT A

0 1

1 0

OutputInput

A NOT A

MULT20015 Elements of Quantum Computing
Lecture 8

Implementing Boolean Functions

AND

NOTAND

Combine several logic gates to create more complex Boolean functions.

A set of (classical) gates is said to be functionally complete (or
“universal”) if every possible truth table (ie. Boolean function) can be
expressed using members of the set.

MULT20015 Elements of Quantum Computing
Lecture 8

Universality in classical logic

A set of (classical) gates is said to be functionally complete (or
“universal”) if every possible truth table (ie. Boolean function) can be
expressed using members of the set.

For example, in classical logic: {AND, OR, NOT} is universal.

AND OR NOT

Every logical circuit can be made from combinations of these gates. In fact,
the NAND gate alone is universal. However, we cannot implement these
gates directly in a quantum computer.

MULT20015 Elements of Quantum Computing
Lecture 8

8.2 Reversible Logic Gates

MULT20015
Lecture 8

MULT20015 Elements of Quantum Computing
Lecture 8

Quantum Computers are Reversible

All the operations we have seen a quantum computer can perform are
reversible.

Eg. CNOT, X, Hadamard.

The only operation we have seen which a quantum computer performs
which is not reversible is measurement.

So quantum computers cannot directly perform AND, OR gates.

MULT20015 Elements of Quantum Computing
Lecture 8

Irreversible Functions

AND or OR are irreversible.

A B A B

0 0 0

0 1 0

1 0 0

1 1 1

We cannot determine the
inputs from the output.

Irreversible functions are cannot be implemented
directly on a quantum computer.

B
AB

MULT20015 Elements of Quantum Computing
Lecture 8

Reversible Logic

Classically, if we would like to calculate some Boolean function, f, we can
construct a circuit out of AND, OR and NOT gates. However, AND and OR
gates are not reversible, and so can’t be implemented in a quantum
computer.

|1i
AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebNBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgRml9c=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebNBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgRml9c=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebNBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgRml9c=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebNBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgRml9c=

|ai
AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAGZsNqjW37s5B14lXkBop0BpUf/rDmKcRKOSSGdPz3AT9jGkUXMKs0k8NJIxP2Ah6lioWgfGz+bkzemGVIQ1jbUshnat/JzIWGTONAtsZMRybVS8X//N6KYYNPxMqSREUXywKU0kxpvnvdCg0cJRTSxjXwt5K+ZhpxtEmtLQl0Mwmk+firaawTjpXdc+te/fXtWajSKhMzsg5uSQeuSFNckdapE04mZAX8krenGfn3flwPhetJaeYOSVLcL5+AVDmmAc=AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAGZsNqjW37s5B14lXkBop0BpUf/rDmKcRKOSSGdPz3AT9jGkUXMKs0k8NJIxP2Ah6lioWgfGz+bkzemGVIQ1jbUshnat/JzIWGTONAtsZMRybVS8X//N6KYYNPxMqSREUXywKU0kxpvnvdCg0cJRTSxjXwt5K+ZhpxtEmtLQl0Mwmk+firaawTjpXdc+te/fXtWajSKhMzsg5uSQeuSFNckdapE04mZAX8krenGfn3flwPhetJaeYOSVLcL5+AVDmmAc=AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAGZsNqjW37s5B14lXkBop0BpUf/rDmKcRKOSSGdPz3AT9jGkUXMKs0k8NJIxP2Ah6lioWgfGz+bkzemGVIQ1jbUshnat/JzIWGTONAtsZMRybVS8X//N6KYYNPxMqSREUXywKU0kxpvnvdCg0cJRTSxjXwt5K+ZhpxtEmtLQl0Mwmk+firaawTjpXdc+te/fXtWajSKhMzsg5uSQeuSFNckdapE04mZAX8krenGfn3flwPhetJaeYOSVLcL5+AVDmmAc=AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAGZsNqjW37s5B14lXkBop0BpUf/rDmKcRKOSSGdPz3AT9jGkUXMKs0k8NJIxP2Ah6lioWgfGz+bkzemGVIQ1jbUshnat/JzIWGTONAtsZMRybVS8X//N6KYYNPxMqSREUXywKU0kxpvnvdCg0cJRTSxjXwt5K+ZhpxtEmtLQl0Mwmk+firaawTjpXdc+te/fXtWajSKhMzsg5uSQeuSFNckdapE04mZAX8krenGfn3flwPhetJaeYOSVLcL5+AVDmmAc=

|āi
AAACBnicbZDPSsNAEMY39V+t/6oevSwWwVNJRLDHghePFWwrNKFMttN26WYTdjdCCb37BF71CbyJV1/DB/A93LQ52NYPBj6+mWGGX5gIro3rfjuljc2t7Z3ybmVv/+DwqHp80tFxqhi2WSxi9RiCRsEltg03Ah8ThRCFArvh5Dbvd59QaR7LBzNNMIhgJPmQMzA28v0JmswPQVGY9as1t+7ORdeNV5gaKdTqV3/8QczSCKVhArTueW5iggyU4UzgrOKnGhNgExhhz1oJEeogm/88oxc2GdBhrGxJQ+fp340MIq2nUWgnIzBjvdrLw/96vdQMG0HGZZIalGxxaJgKamKaA6ADrpAZMbUGmOL2V8rGoIAZi2npSqjA4sm5eKsU1k3nqu65de/+utZsFITK5Iyck0vikRvSJHekRdqEkYS8kFfy5jw7786H87kYLTnFzilZkvP1C8xQmeo=AAACBnicbZDPSsNAEMY39V+t/6oevSwWwVNJRLDHghePFWwrNKFMttN26WYTdjdCCb37BF71CbyJV1/DB/A93LQ52NYPBj6+mWGGX5gIro3rfjuljc2t7Z3ybmVv/+DwqHp80tFxqhi2WSxi9RiCRsEltg03Ah8ThRCFArvh5Dbvd59QaR7LBzNNMIhgJPmQMzA28v0JmswPQVGY9as1t+7ORdeNV5gaKdTqV3/8QczSCKVhArTueW5iggyU4UzgrOKnGhNgExhhz1oJEeogm/88oxc2GdBhrGxJQ+fp340MIq2nUWgnIzBjvdrLw/96vdQMG0HGZZIalGxxaJgKamKaA6ADrpAZMbUGmOL2V8rGoIAZi2npSqjA4sm5eKsU1k3nqu65de/+utZsFITK5Iyck0vikRvSJHekRdqEkYS8kFfy5jw7786H87kYLTnFzilZkvP1C8xQmeo=AAACBnicbZDPSsNAEMY39V+t/6oevSwWwVNJRLDHghePFWwrNKFMttN26WYTdjdCCb37BF71CbyJV1/DB/A93LQ52NYPBj6+mWGGX5gIro3rfjuljc2t7Z3ybmVv/+DwqHp80tFxqhi2WSxi9RiCRsEltg03Ah8ThRCFArvh5Dbvd59QaR7LBzNNMIhgJPmQMzA28v0JmswPQVGY9as1t+7ORdeNV5gaKdTqV3/8QczSCKVhArTueW5iggyU4UzgrOKnGhNgExhhz1oJEeogm/88oxc2GdBhrGxJQ+fp340MIq2nUWgnIzBjvdrLw/96vdQMG0HGZZIalGxxaJgKamKaA6ADrpAZMbUGmOL2V8rGoIAZi2npSqjA4sm5eKsU1k3nqu65de/+utZsFITK5Iyck0vikRvSJHekRdqEkYS8kFfy5jw7786H87kYLTnFzilZkvP1C8xQmeo=AAACBnicbZDPSsNAEMY39V+t/6oevSwWwVNJRLDHghePFWwrNKFMttN26WYTdjdCCb37BF71CbyJV1/DB/A93LQ52NYPBj6+mWGGX5gIro3rfjuljc2t7Z3ybmVv/+DwqHp80tFxqhi2WSxi9RiCRsEltg03Ah8ThRCFArvh5Dbvd59QaR7LBzNNMIhgJPmQMzA28v0JmswPQVGY9as1t+7ORdeNV5gaKdTqV3/8QczSCKVhArTueW5iggyU4UzgrOKnGhNgExhhz1oJEeogm/88oxc2GdBhrGxJQ+fp340MIq2nUWgnIzBjvdrLw/96vdQMG0HGZZIalGxxaJgKamKaA6ADrpAZMbUGmOL2V8rGoIAZi2npSqjA4sm5eKsU1k3nqu65de/+utZsFITK5Iyck0vikRvSJHekRdqEkYS8kFfy5jw7786H87kYLTnFzilZkvP1C8xQmeo=

NOT a

But by use of reversible circuits
and additional bits/qubits, we can
express everything in terms of
reversible gates (such as Toffoli):

MULT20015 Elements of Quantum Computing
Lecture 8

Reversible Logic and the Toffoli Gate

|0i
AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebOBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgLOl9Y=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebOBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgLOl9Y=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebOBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgLOl9Y=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2N0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkRwbVz32yltbG5t75R3K3v7B4dH1eOTjo5TxbDNYhGrx4BqFFxi23Aj8DFRSKNAYDeY3OZ+9wmV5rF8MNME/YiOJA85o8ZK3f4ETebOBtWaW3fnIOvEK0gNCrQG1Z/+MGZphNIwQbXueW5i/Iwqw5nAWaWfakwom9AR9iyVNELtZ/NzZ+TCKkMSxsqWNGSu/p3IaKT1NApsZ0TNWK96ufif10tN2PAzLpPUoGSLRWEqiIlJ/jsZcoXMiKkllClubyVsTBVlxia0tCVQ1CaT5+KtprBOOld1z61799e1ZqNIqAxncA6X4MENNOEOWtAGBhN4gVd4c56dd+fD+Vy0lpxi5hSW4Hz9AgLOl9Y=

|bi
AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAWTAbVGtu3Z2DrhOvIDVSoDWo/vSHMU8jUMglM6bnuQn6GdMouIRZpZ8aSBifsBH0LFUsAuNn83Nn9MIqQxrG2pZCOlf/TmQsMmYaBbYzYjg2q14u/uf1UgwbfiZUkiIovlgUppJiTPPf6VBo4CinljCuhb2V8jHTjKNNaGlLoJlNJs/FW01hnXSu6p5b9+6va81GkVCZnJFzckk8ckOa5I60SJtwMiEv5JW8Oc/Ou/PhfC5aS04xc0qW4Hz9AlJ+mAg=AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAWTAbVGtu3Z2DrhOvIDVSoDWo/vSHMU8jUMglM6bnuQn6GdMouIRZpZ8aSBifsBH0LFUsAuNn83Nn9MIqQxrG2pZCOlf/TmQsMmYaBbYzYjg2q14u/uf1UgwbfiZUkiIovlgUppJiTPPf6VBo4CinljCuhb2V8jHTjKNNaGlLoJlNJs/FW01hnXSu6p5b9+6va81GkVCZnJFzckk8ckOa5I60SJtwMiEv5JW8Oc/Ou/PhfC5aS04xc0qW4Hz9AlJ+mAg=AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAWTAbVGtu3Z2DrhOvIDVSoDWo/vSHMU8jUMglM6bnuQn6GdMouIRZpZ8aSBifsBH0LFUsAuNn83Nn9MIqQxrG2pZCOlf/TmQsMmYaBbYzYjg2q14u/uf1UgwbfiZUkiIovlgUppJiTPPf6VBo4CinljCuhb2V8jHTjKNNaGlLoJlNJs/FW01hnXSu6p5b9+6va81GkVCZnJFzckk8ckOa5I60SJtwMiEv5JW8Oc/Ou/PhfC5aS04xc0qW4Hz9AlJ+mAg=AAACAXicbVBNS8NAEN3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2k3bpZhN2J0IJPfkLvOov8CZe/SX+AP+HmzYH2/pg4PHeDDPzgkQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJx8Sp5tDmsYz1Y8AMSKGgjQIlPCYaWBRI6AaT29zvPoE2IlYPOE3Aj9hIiVBwhlbq9ieAWTAbVGtu3Z2DrhOvIDVSoDWo/vSHMU8jUMglM6bnuQn6GdMouIRZpZ8aSBifsBH0LFUsAuNn83Nn9MIqQxrG2pZCOlf/TmQsMmYaBbYzYjg2q14u/uf1UgwbfiZUkiIovlgUppJiTPPf6VBo4CinljCuhb2V8jHTjKNNaGlLoJlNJs/FW01hnXSu6p5b9+6va81GkVCZnJFzckk8ckOa5I60SJtwMiEv5JW8Oc/Ou/PhfC5aS04xc0qW4Hz9AlJ+mAg=

a AND b

|a ^ bi
AAACC3icbZDLSsNAFIYn9VbrpVGXbgaL4KokIthlwY3LCvYCTSgnk0k7dDIJMxOhhD6CT+BWn8CduPUhfADfw0mbhW394cDPf87hHL4g5Uxpx/m2KlvbO7t71f3aweHRcd0+Oe2pJJOEdknCEzkIQFHOBO1qpjkdpJJCHHDaD6Z3Rb//RKViiXjUs5T6MYwFixgBbaKRXfemVOeAPQ4ixMF8ZDecprMQ3jRuaRqoVGdk/3hhQrKYCk04KDV0nVT7OUjNCKfzmpcpmgKZwpgOjRUQU+Xni8fn+NIkIY4SaUpovEj/buQQKzWLAzMZg56o9V4R/tcbZjpq+TkTaaapIMtDUcaxTnBBAYdMUqL5zBggkplfMZmABKINq5UrgQRDqODirlPYNL3rpus03YebRrtVEqqic3SBrpCLblEb3aMO6iKCMvSCXtGb9Wy9Wx/W53K0YpU7Z2hF1tcvOoSbJQ==AAACC3icbZDLSsNAFIYn9VbrpVGXbgaL4KokIthlwY3LCvYCTSgnk0k7dDIJMxOhhD6CT+BWn8CduPUhfADfw0mbhW394cDPf87hHL4g5Uxpx/m2KlvbO7t71f3aweHRcd0+Oe2pJJOEdknCEzkIQFHOBO1qpjkdpJJCHHDaD6Z3Rb//RKViiXjUs5T6MYwFixgBbaKRXfemVOeAPQ4ixMF8ZDecprMQ3jRuaRqoVGdk/3hhQrKYCk04KDV0nVT7OUjNCKfzmpcpmgKZwpgOjRUQU+Xni8fn+NIkIY4SaUpovEj/buQQKzWLAzMZg56o9V4R/tcbZjpq+TkTaaapIMtDUcaxTnBBAYdMUqL5zBggkplfMZmABKINq5UrgQRDqODirlPYNL3rpus03YebRrtVEqqic3SBrpCLblEb3aMO6iKCMvSCXtGb9Wy9Wx/W53K0YpU7Z2hF1tcvOoSbJQ==AAACC3icbZDLSsNAFIYn9VbrpVGXbgaL4KokIthlwY3LCvYCTSgnk0k7dDIJMxOhhD6CT+BWn8CduPUhfADfw0mbhW394cDPf87hHL4g5Uxpx/m2KlvbO7t71f3aweHRcd0+Oe2pJJOEdknCEzkIQFHOBO1qpjkdpJJCHHDaD6Z3Rb//RKViiXjUs5T6MYwFixgBbaKRXfemVOeAPQ4ixMF8ZDecprMQ3jRuaRqoVGdk/3hhQrKYCk04KDV0nVT7OUjNCKfzmpcpmgKZwpgOjRUQU+Xni8fn+NIkIY4SaUpovEj/buQQKzWLAzMZg56o9V4R/tcbZjpq+TkTaaapIMtDUcaxTnBBAYdMUqL5zBggkplfMZmABKINq5UrgQRDqODirlPYNL3rpus03YebRrtVEqqic3SBrpCLblEb3aMO6iKCMvSCXtGb9Wy9Wx/W53K0YpU7Z2hF1tcvOoSbJQ==AAACC3icbZDLSsNAFIYn9VbrpVGXbgaL4KokIthlwY3LCvYCTSgnk0k7dDIJMxOhhD6CT+BWn8CduPUhfADfw0mbhW394cDPf87hHL4g5Uxpx/m2KlvbO7t71f3aweHRcd0+Oe2pJJOEdknCEzkIQFHOBO1qpjkdpJJCHHDaD6Z3Rb//RKViiXjUs5T6MYwFixgBbaKRXfemVOeAPQ4ixMF8ZDecprMQ3jRuaRqoVGdk/3hhQrKYCk04KDV0nVT7OUjNCKfzmpcpmgKZwpgOjRUQU+Xni8fn+NIkIY4SaUpovEj/buQQKzWLAzMZg56o9V4R/tcbZjpq+TkTaaapIMtDUcaxTnBBAYdMUqL5zBggkplfMZmABKINq5UrgQRDqODirlPYNL3rpus03YebRrtVEqqic3SBrpCLblEb3aMO6iKCMvSCXtGb9Wy9Wx/W53K0YpU7Z2hF1tcvOoSbJQ==

a XOR b

(NOT a) OR (NOT b)

|a� bi
AAACDHicbZBLSgNBEIZ74ivG16hLN41BcBVmRDDLgBuXEcwDMkPo6VSSJj3dQ3dPIAy5gidwqydwJ269gwfwHvYkszCJPxT8/FVFFV+UcKaN5307pa3tnd298n7l4PDo+MQ9PWtrmSoKLSq5VN2IaOBMQMsww6GbKCBxxKETTe7zfmcKSjMpnswsgTAmI8GGjBJjo77rBhMwGcGBTHiqcTTvu1Wv5i2EN41fmCoq1Oy7P8FA0jQGYSgnWvd8LzFhRpRhlMO8EqQaEkInZAQ9awWJQYfZ4vM5vrLJAA+lsiUMXqR/NzISaz2LIzsZEzPW6708/K/XS82wHmZMJKkBQZeHhinHRuIcAx4wBdTwmTWEKmZ/xXRMFKHGwlq5EiliEeVc/HUKm6Z9U/O9mv94W23UC0JldIEu0TXy0R1qoAfURC1E0RS9oFf05jw7786H87kcLTnFzjlakfP1C1Gqm8M=AAACDHicbZBLSgNBEIZ74ivG16hLN41BcBVmRDDLgBuXEcwDMkPo6VSSJj3dQ3dPIAy5gidwqydwJ269gwfwHvYkszCJPxT8/FVFFV+UcKaN5307pa3tnd298n7l4PDo+MQ9PWtrmSoKLSq5VN2IaOBMQMsww6GbKCBxxKETTe7zfmcKSjMpnswsgTAmI8GGjBJjo77rBhMwGcGBTHiqcTTvu1Wv5i2EN41fmCoq1Oy7P8FA0jQGYSgnWvd8LzFhRpRhlMO8EqQaEkInZAQ9awWJQYfZ4vM5vrLJAA+lsiUMXqR/NzISaz2LIzsZEzPW6708/K/XS82wHmZMJKkBQZeHhinHRuIcAx4wBdTwmTWEKmZ/xXRMFKHGwlq5EiliEeVc/HUKm6Z9U/O9mv94W23UC0JldIEu0TXy0R1qoAfURC1E0RS9oFf05jw7786H87kcLTnFzjlakfP1C1Gqm8M=AAACDHicbZBLSgNBEIZ74ivG16hLN41BcBVmRDDLgBuXEcwDMkPo6VSSJj3dQ3dPIAy5gidwqydwJ269gwfwHvYkszCJPxT8/FVFFV+UcKaN5307pa3tnd298n7l4PDo+MQ9PWtrmSoKLSq5VN2IaOBMQMsww6GbKCBxxKETTe7zfmcKSjMpnswsgTAmI8GGjBJjo77rBhMwGcGBTHiqcTTvu1Wv5i2EN41fmCoq1Oy7P8FA0jQGYSgnWvd8LzFhRpRhlMO8EqQaEkInZAQ9awWJQYfZ4vM5vrLJAA+lsiUMXqR/NzISaz2LIzsZEzPW6708/K/XS82wHmZMJKkBQZeHhinHRuIcAx4wBdTwmTWEKmZ/xXRMFKHGwlq5EiliEeVc/HUKm6Z9U/O9mv94W23UC0JldIEu0TXy0R1qoAfURC1E0RS9oFf05jw7786H87kcLTnFzjlakfP1C1Gqm8M=AAACDHicbZBLSgNBEIZ74ivG16hLN41BcBVmRDDLgBuXEcwDMkPo6VSSJj3dQ3dPIAy5gidwqydwJ269gwfwHvYkszCJPxT8/FVFFV+UcKaN5307pa3tnd298n7l4PDo+MQ9PWtrmSoKLSq5VN2IaOBMQMsww6GbKCBxxKETTe7zfmcKSjMpnswsgTAmI8GGjBJjo77rBhMwGcGBTHiqcTTvu1Wv5i2EN41fmCoq1Oy7P8FA0jQGYSgnWvd8LzFhRpRhlMO8EqQaEkInZAQ9awWJQYfZ4vM5vrLJAA+lsiUMXqR/NzISaz2LIzsZEzPW6708/K/XS82wHmZMJKkBQZeHhinHRuIcAx4wBdTwmTWEKmZ/xXRMFKHGwlq5EiliEeVc/HUKm6Z9U/O9mv94W23UC0JldIEu0TXy0R1qoAfURC1E0RS9oFf05jw7786H87kcLTnFzjlakfP1C1Gqm8M=

|¬a _ ¬bi
AAACFnicbVDLSgMxFM34rPU16k43wSK4KjMi2GXBjcsK9gGdUjJppg3NJENyRyhDwc/wC9zqF7gTt279AP/DTDsL23pXJ+ecy7k5YSK4Ac/7dtbWNza3tks75d29/YND9+i4ZVSqKWtSJZTuhMQwwSVrAgfBOolmJA4Fa4fj21xvPzJtuJIPMElYLyZDySNOCViq754GYwZZIKQCTHBg7Xj+CKd9t+JVvdngVeAXoIKKafTdn2CgaBozCVQQY7q+l0AvIxo4FWxaDlLDEkLHZMi6FkoSM9PLZn+Y4gvLDHBk8yMlAc/YvxsZiY2ZxKF1xgRGZlnLyf+0bgpRrZdxmaTAJJ0HRanAoHBeCB5wzSiIiQWEam5vxXRENKFga1tICTWxZeW9+MstrILWVdX3qv79daVeKxoqoTN0ji6Rj25QHd2hBmoiip7QC3pFb86z8+58OJ9z65pT7JyghXG+fgG3Tp+zAAACFnicbVDLSgMxFM34rPU16k43wSK4KjMi2GXBjcsK9gGdUjJppg3NJENyRyhDwc/wC9zqF7gTt279AP/DTDsL23pXJ+ecy7k5YSK4Ac/7dtbWNza3tks75d29/YND9+i4ZVSqKWtSJZTuhMQwwSVrAgfBOolmJA4Fa4fj21xvPzJtuJIPMElYLyZDySNOCViq754GYwZZIKQCTHBg7Xj+CKd9t+JVvdngVeAXoIKKafTdn2CgaBozCVQQY7q+l0AvIxo4FWxaDlLDEkLHZMi6FkoSM9PLZn+Y4gvLDHBk8yMlAc/YvxsZiY2ZxKF1xgRGZlnLyf+0bgpRrZdxmaTAJJ0HRanAoHBeCB5wzSiIiQWEam5vxXRENKFga1tICTWxZeW9+MstrILWVdX3qv79daVeKxoqoTN0ji6Rj25QHd2hBmoiip7QC3pFb86z8+58OJ9z65pT7JyghXG+fgG3Tp+zAAACFnicbVDLSgMxFM34rPU16k43wSK4KjMi2GXBjcsK9gGdUjJppg3NJENyRyhDwc/wC9zqF7gTt279AP/DTDsL23pXJ+ecy7k5YSK4Ac/7dtbWNza3tks75d29/YND9+i4ZVSqKWtSJZTuhMQwwSVrAgfBOolmJA4Fa4fj21xvPzJtuJIPMElYLyZDySNOCViq754GYwZZIKQCTHBg7Xj+CKd9t+JVvdngVeAXoIKKafTdn2CgaBozCVQQY7q+l0AvIxo4FWxaDlLDEkLHZMi6FkoSM9PLZn+Y4gvLDHBk8yMlAc/YvxsZiY2ZxKF1xgRGZlnLyf+0bgpRrZdxmaTAJJ0HRanAoHBeCB5wzSiIiQWEam5vxXRENKFga1tICTWxZeW9+MstrILWVdX3qv79daVeKxoqoTN0ji6Rj25QHd2hBmoiip7QC3pFb86z8+58OJ9z65pT7JyghXG+fgG3Tp+zAAACFnicbVDLSgMxFM34rPU16k43wSK4KjMi2GXBjcsK9gGdUjJppg3NJENyRyhDwc/wC9zqF7gTt279AP/DTDsL23pXJ+ecy7k5YSK4Ac/7dtbWNza3tks75d29/YND9+i4ZVSqKWtSJZTuhMQwwSVrAgfBOolmJA4Fa4fj21xvPzJtuJIPMElYLyZDySNOCViq754GYwZZIKQCTHBg7Xj+CKd9t+JVvdngVeAXoIKKafTdn2CgaBozCVQQY7q+l0AvIxo4FWxaDlLDEkLHZMi6FkoSM9PLZn+Y4gvLDHBk8yMlAc/YvxsZiY2ZxKF1xgRGZlnLyf+0bgpRrZdxmaTAJJ0HRanAoHBeCB5wzSiIiQWEam5vxXRENKFga1tICTWxZeW9+MstrILWVdX3qv79daVeKxoqoTN0ji6Rj25QHd2hBmoiip7QC3pFb86z8+58OJ9z65pT7JyghXG+fgG3Tp+z

The Toffoli gate is universal and reversible. In principle every classical Boolean
function can be written in terms of reversible gates (such as Toffoli) which can
be implemented on a quantum computer.

a b a ⋀ b

0 0 0

0 1 0

1 0 0

1 1 1

a b a ⊕ b

0 0 0

0 1 1

1 0 1

1 1 0

a b ¬a ⋁ ¬b

0 0 1

0 1 1

1 0 1

1 1 0

MULT20015 Elements of Quantum Computing
Lecture 8

Implementing irreversible functions

Another strategy which you often see to make an irreversible function
reversible is simply to propagate the inputs:

|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=

You will see this pattern in several of the quantum algorithms we will study.

Input Repeated at
output

|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

MULT20015 Elements of Quantum Computing
Lecture 8

Implementing irreversible functions

Another strategy which you often see to make an irreversible function
reversible is simply to propagate the inputs:

|yi
AAACAXicbVBNS8NAEJ3Ur1q/qh69BIvgqSQi2GPBi8cKthXaUDbbSbtkswm7GyGEnvwFXvUXeBOv/hJ/gP/DTZuDbX0w8Hhvhpl5fsKZ0o7zbVU2Nre2d6q7tb39g8Oj+vFJT8WppNilMY/lo08Uciawq5nm+JhIJJHPse+Ht4Xff0KpWCwedJagF5GJYAGjRBupPwxR59lsVG84TWcOe524JWlAic6o/jMcxzSNUGjKiVID10m0lxOpGeU4qw1ThQmhIZngwFBBIlRePj93Zl8YZWwHsTQltD1X/07kJFIqi3zTGRE9VateIf7nDVIdtLyciSTVKOhiUZByW8d28bs9ZhKp5pkhhEpmbrXplEhCtUloaYsviUmmyMVdTWGd9K6artN0768b7VaZUBXO4BwuwYUbaMMddKALFEJ4gVd4s56td+vD+ly0Vqxy5hSWYH39AncmmB8=AAACAXicbVBNS8NAEJ3Ur1q/qh69BIvgqSQi2GPBi8cKthXaUDbbSbtkswm7GyGEnvwFXvUXeBOv/hJ/gP/DTZuDbX0w8Hhvhpl5fsKZ0o7zbVU2Nre2d6q7tb39g8Oj+vFJT8WppNilMY/lo08Uciawq5nm+JhIJJHPse+Ht4Xff0KpWCwedJagF5GJYAGjRBupPwxR59lsVG84TWcOe524JWlAic6o/jMcxzSNUGjKiVID10m0lxOpGeU4qw1ThQmhIZngwFBBIlRePj93Zl8YZWwHsTQltD1X/07kJFIqi3zTGRE9VateIf7nDVIdtLyciSTVKOhiUZByW8d28bs9ZhKp5pkhhEpmbrXplEhCtUloaYsviUmmyMVdTWGd9K6artN0768b7VaZUBXO4BwuwYUbaMMddKALFEJ4gVd4s56td+vD+ly0Vqxy5hSWYH39AncmmB8=AAACAXicbVBNS8NAEJ3Ur1q/qh69BIvgqSQi2GPBi8cKthXaUDbbSbtkswm7GyGEnvwFXvUXeBOv/hJ/gP/DTZuDbX0w8Hhvhpl5fsKZ0o7zbVU2Nre2d6q7tb39g8Oj+vFJT8WppNilMY/lo08Uciawq5nm+JhIJJHPse+Ht4Xff0KpWCwedJagF5GJYAGjRBupPwxR59lsVG84TWcOe524JWlAic6o/jMcxzSNUGjKiVID10m0lxOpGeU4qw1ThQmhIZngwFBBIlRePj93Zl8YZWwHsTQltD1X/07kJFIqi3zTGRE9VateIf7nDVIdtLyciSTVKOhiUZByW8d28bs9ZhKp5pkhhEpmbrXplEhCtUloaYsviUmmyMVdTWGd9K6artN0768b7VaZUBXO4BwuwYUbaMMddKALFEJ4gVd4s56td+vD+ly0Vqxy5hSWYH39AncmmB8=AAACAXicbVBNS8NAEJ3Ur1q/qh69BIvgqSQi2GPBi8cKthXaUDbbSbtkswm7GyGEnvwFXvUXeBOv/hJ/gP/DTZuDbX0w8Hhvhpl5fsKZ0o7zbVU2Nre2d6q7tb39g8Oj+vFJT8WppNilMY/lo08Uciawq5nm+JhIJJHPse+Ht4Xff0KpWCwedJagF5GJYAGjRBupPwxR59lsVG84TWcOe524JWlAic6o/jMcxzSNUGjKiVID10m0lxOpGeU4qw1ThQmhIZngwFBBIlRePj93Zl8YZWwHsTQltD1X/07kJFIqi3zTGRE9VateIf7nDVIdtLyciSTVKOhiUZByW8d28bs9ZhKp5pkhhEpmbrXplEhCtUloaYsviUmmyMVdTWGd9K6artN0768b7VaZUBXO4BwuwYUbaMMddKALFEJ4gVd4s56td+vD+ly0Vqxy5hSWYH39AncmmB8=

|y � f(x)i
AAACD3icbZDLSsNAFIYnXmu9Rbt0M1iEuimJCHZZcOOygr1AE8pketIOnWTCzEQMoQ/hE7jVJ3Anbn0EH8D3cNJ2YVt/OPDzn3M4hy9IOFPacb6tjc2t7Z3d0l55/+Dw6Ng+Oe0okUoKbSq4kL2AKOAshrZmmkMvkUCigEM3mNwW/e4jSMVE/KCzBPyIjGIWMkq0iQZ2xZuAzjPsiYSnCoe1p8vpwK46dWcmvG7chamihVoD+8cbCppGEGvKiVJ910m0nxOpGeUwLXupgoTQCRlB39iYRKD8fPb8FF+YZIhDIU3FGs/Svxs5iZTKosBMRkSP1WqvCP/r9VMdNvycxUmqIabzQ2HKsRa4IIGHTALVPDOGUMnMr5iOiSRUG15LVwJJDKWCi7tKYd10ruquU3fvr6vNxoJQCZ2hc1RDLrpBTXSHWqiNKMrQC3pFb9az9W59WJ/z0Q1rsVNBS7K+fgFBXZzGAAACD3icbZDLSsNAFIYnXmu9Rbt0M1iEuimJCHZZcOOygr1AE8pketIOnWTCzEQMoQ/hE7jVJ3Anbn0EH8D3cNJ2YVt/OPDzn3M4hy9IOFPacb6tjc2t7Z3d0l55/+Dw6Ng+Oe0okUoKbSq4kL2AKOAshrZmmkMvkUCigEM3mNwW/e4jSMVE/KCzBPyIjGIWMkq0iQZ2xZuAzjPsiYSnCoe1p8vpwK46dWcmvG7chamihVoD+8cbCppGEGvKiVJ910m0nxOpGeUwLXupgoTQCRlB39iYRKD8fPb8FF+YZIhDIU3FGs/Svxs5iZTKosBMRkSP1WqvCP/r9VMdNvycxUmqIabzQ2HKsRa4IIGHTALVPDOGUMnMr5iOiSRUG15LVwJJDKWCi7tKYd10ruquU3fvr6vNxoJQCZ2hc1RDLrpBTXSHWqiNKMrQC3pFb9az9W59WJ/z0Q1rsVNBS7K+fgFBXZzGAAACD3icbZDLSsNAFIYnXmu9Rbt0M1iEuimJCHZZcOOygr1AE8pketIOnWTCzEQMoQ/hE7jVJ3Anbn0EH8D3cNJ2YVt/OPDzn3M4hy9IOFPacb6tjc2t7Z3d0l55/+Dw6Ng+Oe0okUoKbSq4kL2AKOAshrZmmkMvkUCigEM3mNwW/e4jSMVE/KCzBPyIjGIWMkq0iQZ2xZuAzjPsiYSnCoe1p8vpwK46dWcmvG7chamihVoD+8cbCppGEGvKiVJ910m0nxOpGeUwLXupgoTQCRlB39iYRKD8fPb8FF+YZIhDIU3FGs/Svxs5iZTKosBMRkSP1WqvCP/r9VMdNvycxUmqIabzQ2HKsRa4IIGHTALVPDOGUMnMr5iOiSRUG15LVwJJDKWCi7tKYd10ruquU3fvr6vNxoJQCZ2hc1RDLrpBTXSHWqiNKMrQC3pFb9az9W59WJ/z0Q1rsVNBS7K+fgFBXZzGAAACD3icbZDLSsNAFIYnXmu9Rbt0M1iEuimJCHZZcOOygr1AE8pketIOnWTCzEQMoQ/hE7jVJ3Anbn0EH8D3cNJ2YVt/OPDzn3M4hy9IOFPacb6tjc2t7Z3d0l55/+Dw6Ng+Oe0okUoKbSq4kL2AKOAshrZmmkMvkUCigEM3mNwW/e4jSMVE/KCzBPyIjGIWMkq0iQZ2xZuAzjPsiYSnCoe1p8vpwK46dWcmvG7chamihVoD+8cbCppGEGvKiVJ910m0nxOpGeUwLXupgoTQCRlB39iYRKD8fPb8FF+YZIhDIU3FGs/Svxs5iZTKosBMRkSP1WqvCP/r9VMdNvycxUmqIabzQ2HKsRa4IIGHTALVPDOGUMnMr5iOiSRUG15LVwJJDKWCi7tKYd10ruquU3fvr6vNxoJQCZ2hc1RDLrpBTXSHWqiNKMrQC3pFb9az9W59WJ/z0Q1rsVNBS7K+fgFBXZzG

Add (bit-by-bit modulo 2)
input and calculated f(x)

Must deal with all possible
inputs, not just 0.

You will see this pattern in several of the quantum algorithms we will study.

Input Repeated at
output

MULT20015 Elements of Quantum Computing
Lecture 8

8.3 Arithmetic on a Quantum Computer

MULT20015
Lecture 8

MULT20015 Elements of Quantum Computing
Lecture 8

One Bit Adder

We can, for example, implement a one bit adder using only reversible gates:

|ai
AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS+idzCZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUM95ksYx1JwDDpVC8iQIl7ySaQxRI3g7GtzO//cS1EbF6wEnC/QiGSoSCAVqp1RtzpNAvV9yqOwddJ15OKiRHo1/+6Q1ilkZcIZNgTNdzE/Qz0CiY5NNSLzU8ATaGIe9aqiDixs/m107phVUGNIy1LYV0rv6dyCAyZhIFtjMCHJlVbyb+53VTDGt+JlSSIldssShMJcWYzl6nA6E5QzmxBJgW9lbKRqCBoQ1oaUugwQYztbl4qymsk9ZV1XOr3v11pV7LEyqSM3JOLolHbkid3JEGaRJGHskLeSVvzrPz7nw4n4vWgpPPnJIlOF+/0YiXJQ==AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS+idzCZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUM95ksYx1JwDDpVC8iQIl7ySaQxRI3g7GtzO//cS1EbF6wEnC/QiGSoSCAVqp1RtzpNAvV9yqOwddJ15OKiRHo1/+6Q1ilkZcIZNgTNdzE/Qz0CiY5NNSLzU8ATaGIe9aqiDixs/m107phVUGNIy1LYV0rv6dyCAyZhIFtjMCHJlVbyb+53VTDGt+JlSSIldssShMJcWYzl6nA6E5QzmxBJgW9lbKRqCBoQ1oaUugwQYztbl4qymsk9ZV1XOr3v11pV7LEyqSM3JOLolHbkid3JEGaRJGHskLeSVvzrPz7nw4n4vWgpPPnJIlOF+/0YiXJQ==AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS+idzCZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUM95ksYx1JwDDpVC8iQIl7ySaQxRI3g7GtzO//cS1EbF6wEnC/QiGSoSCAVqp1RtzpNAvV9yqOwddJ15OKiRHo1/+6Q1ilkZcIZNgTNdzE/Qz0CiY5NNSLzU8ATaGIe9aqiDixs/m107phVUGNIy1LYV0rv6dyCAyZhIFtjMCHJlVbyb+53VTDGt+JlSSIldssShMJcWYzl6nA6E5QzmxBJgW9lbKRqCBoQ1oaUugwQYztbl4qymsk9ZV1XOr3v11pV7LEyqSM3JOLolHbkid3JEGaRJGHskLeSVvzrPz7nw4n4vWgpPPnJIlOF+/0YiXJQ==AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS+idzCZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUM95ksYx1JwDDpVC8iQIl7ySaQxRI3g7GtzO//cS1EbF6wEnC/QiGSoSCAVqp1RtzpNAvV9yqOwddJ15OKiRHo1/+6Q1ilkZcIZNgTNdzE/Qz0CiY5NNSLzU8ATaGIe9aqiDixs/m107phVUGNIy1LYV0rv6dyCAyZhIFtjMCHJlVbyb+53VTDGt+JlSSIldssShMJcWYzl6nA6E5QzmxBJgW9lbKRqCBoQ1oaUugwQYztbl4qymsk9ZV1XOr3v11pV7LEyqSM3JOLolHbkid3JEGaRJGHskLeSVvzrPz7nw4n4vWgpPPnJIlOF+/0YiXJQ==

|bi
AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUc2jyWMa6EzADUihookAJnUQDiwIJ7WB8O/PbT6CNiNUDThLwIzZUIhScoZVavTEgDfrlilt156DrxMtJheRo9Ms/vUHM0wgUcsmM6Xpugn7GNAouYVrqpQYSxsdsCF1LFYvA+Nn82im9sMqAhrG2pZDO1b8TGYuMmUSB7YwYjsyqNxP/87ophjU/EypJERRfLApTSTGms9fpQGjgKCeWMK6FvZXyEdOMow1oaUugmQ1manPxVlNYJ62rqudWvfvrSr2WJ1QkZ+ScXBKP3JA6uSMN0iScPJIX8krenGfn3flwPhetBSefOSVLcL5+AdMflyY=AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUc2jyWMa6EzADUihookAJnUQDiwIJ7WB8O/PbT6CNiNUDThLwIzZUIhScoZVavTEgDfrlilt156DrxMtJheRo9Ms/vUHM0wgUcsmM6Xpugn7GNAouYVrqpQYSxsdsCF1LFYvA+Nn82im9sMqAhrG2pZDO1b8TGYuMmUSB7YwYjsyqNxP/87ophjU/EypJERRfLApTSTGms9fpQGjgKCeWMK6FvZXyEdOMow1oaUugmQ1manPxVlNYJ62rqudWvfvrSr2WJ1QkZ+ScXBKP3JA6uSMN0iScPJIX8krenGfn3flwPhetBSefOSVLcL5+AdMflyY=AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUc2jyWMa6EzADUihookAJnUQDiwIJ7WB8O/PbT6CNiNUDThLwIzZUIhScoZVavTEgDfrlilt156DrxMtJheRo9Ms/vUHM0wgUcsmM6Xpugn7GNAouYVrqpQYSxsdsCF1LFYvA+Nn82im9sMqAhrG2pZDO1b8TGYuMmUSB7YwYjsyqNxP/87ophjU/EypJERRfLApTSTGms9fpQGjgKCeWMK6FvZXyEdOMow1oaUugmQ1manPxVlNYJ62rqudWvfvrSr2WJ1QkZ+ScXBKP3JA6uSMN0iScPJIX8krenGfn3flwPhetBSefOSVLcL5+AdMflyY=AAACAHicbVDLSgNBEJyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmV4hLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSKFQdf9dgobm1vbO8Xd0t7+weFR+fikZeJUc2jyWMa6EzADUihookAJnUQDiwIJ7WB8O/PbT6CNiNUDThLwIzZUIhScoZVavTEgDfrlilt156DrxMtJheRo9Ms/vUHM0wgUcsmM6Xpugn7GNAouYVrqpQYSxsdsCF1LFYvA+Nn82im9sMqAhrG2pZDO1b8TGYuMmUSB7YwYjsyqNxP/87ophjU/EypJERRfLApTSTGms9fpQGjgKCeWMK6FvZXyEdOMow1oaUugmQ1manPxVlNYJ62rqudWvfvrSr2WJ1QkZ+ScXBKP3JA6uSMN0iScPJIX8krenGfn3flwPhetBSefOSVLcL5+AdMflyY=

|0i
AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=

|a+ bi
AAACBHicbVDLSgNBEJyNrxhfUY9eBoMgCGFXBHMMePEYwSRisoTeySQZMju7zPQKYcnVL/CqX+BNvPoffoD/4WyyB5NY0FBUddPdFcRSGHTdb6ewtr6xuVXcLu3s7u0flA+PWiZKNONNFslIPwRguBSKN1Gg5A+x5hAGkreD8U3mt5+4NiJS9ziJuR/CUImBYIBWeuyOOdIULoJpr1xxq+4MdJV4OamQHI1e+afbj1gScoVMgjEdz43RT0GjYJJPS93E8BjYGIa8Y6mCkBs/nV08pWdW6dNBpG0ppDP170QKoTGTMLCdIeDILHuZ+J/XSXBQ81Oh4gS5YvNFg0RSjGj2Pu0LzRnKiSXAtLC3UjYCDQxtSAtbAg02nCwXbzmFVdK6rHpu1bu7qtRreUJFckJOyTnxyDWpk1vSIE3CiCIv5JW8Oc/Ou/PhfM5bC04+c0wW4Hz9Atr/mNI=AAACBHicbVDLSgNBEJyNrxhfUY9eBoMgCGFXBHMMePEYwSRisoTeySQZMju7zPQKYcnVL/CqX+BNvPoffoD/4WyyB5NY0FBUddPdFcRSGHTdb6ewtr6xuVXcLu3s7u0flA+PWiZKNONNFslIPwRguBSKN1Gg5A+x5hAGkreD8U3mt5+4NiJS9ziJuR/CUImBYIBWeuyOOdIULoJpr1xxq+4MdJV4OamQHI1e+afbj1gScoVMgjEdz43RT0GjYJJPS93E8BjYGIa8Y6mCkBs/nV08pWdW6dNBpG0ppDP170QKoTGTMLCdIeDILHuZ+J/XSXBQ81Oh4gS5YvNFg0RSjGj2Pu0LzRnKiSXAtLC3UjYCDQxtSAtbAg02nCwXbzmFVdK6rHpu1bu7qtRreUJFckJOyTnxyDWpk1vSIE3CiCIv5JW8Oc/Ou/PhfM5bC04+c0wW4Hz9Atr/mNI=AAACBHicbVDLSgNBEJyNrxhfUY9eBoMgCGFXBHMMePEYwSRisoTeySQZMju7zPQKYcnVL/CqX+BNvPoffoD/4WyyB5NY0FBUddPdFcRSGHTdb6ewtr6xuVXcLu3s7u0flA+PWiZKNONNFslIPwRguBSKN1Gg5A+x5hAGkreD8U3mt5+4NiJS9ziJuR/CUImBYIBWeuyOOdIULoJpr1xxq+4MdJV4OamQHI1e+afbj1gScoVMgjEdz43RT0GjYJJPS93E8BjYGIa8Y6mCkBs/nV08pWdW6dNBpG0ppDP170QKoTGTMLCdIeDILHuZ+J/XSXBQ81Oh4gS5YvNFg0RSjGj2Pu0LzRnKiSXAtLC3UjYCDQxtSAtbAg02nCwXbzmFVdK6rHpu1bu7qtRreUJFckJOyTnxyDWpk1vSIE3CiCIv5JW8Oc/Ou/PhfM5bC04+c0wW4Hz9Atr/mNI=AAACBHicbVDLSgNBEJyNrxhfUY9eBoMgCGFXBHMMePEYwSRisoTeySQZMju7zPQKYcnVL/CqX+BNvPoffoD/4WyyB5NY0FBUddPdFcRSGHTdb6ewtr6xuVXcLu3s7u0flA+PWiZKNONNFslIPwRguBSKN1Gg5A+x5hAGkreD8U3mt5+4NiJS9ziJuR/CUImBYIBWeuyOOdIULoJpr1xxq+4MdJV4OamQHI1e+afbj1gScoVMgjEdz43RT0GjYJJPS93E8BjYGIa8Y6mCkBs/nV08pWdW6dNBpG0ppDP170QKoTGTMLCdIeDILHuZ+J/XSXBQ81Oh4gS5YvNFg0RSjGj2Pu0LzRnKiSXAtLC3UjYCDQxtSAtbAg02nCwXbzmFVdK6rHpu1bu7qtRreUJFckJOyTnxyDWpk1vSIE3CiCIv5JW8Oc/Ou/PhfM5bC04+c0wW4Hz9Atr/mNI=

|carryi
AAACEXicbVDLSsNAFJ3UV62vqLhyM1gEVyURwS4LblxWsA9oQrmZTtuhM0mYmQgh5Cv8Arf6Be7ErV/gB/gfTtosbOuBC4dz7uUeThBzprTjfFuVjc2t7Z3qbm1v/+DwyD4+6aookYR2SMQj2Q9AUc5C2tFMc9qPJQURcNoLZneF33uiUrEofNRpTH0Bk5CNGQFtpKF95s2oxpknQE+lyAhImeb50K47DWcOvE7cktRRifbQ/vFGEUkEDTXhoNTAdWLtZyA1I5zmNS9RNAYygwkdGBqCoMrP5vFzfGmUER5H0kyo8Vz9e5GBUCoVgdksYqpVrxD/8waJHjf9jIVxomlIFo/GCcc6wkUXeMQkJZqnhgCRzGTFZAoSiDaNLX0JJJieil7c1RbWSfe64ToN9+Gm3mqWDVXRObpAV8hFt6iF7lEbdRBBGXpBr+jNerberQ/rc7FascqbU7QE6+sXPQOegQ==AAACEXicbVDLSsNAFJ3UV62vqLhyM1gEVyURwS4LblxWsA9oQrmZTtuhM0mYmQgh5Cv8Arf6Be7ErV/gB/gfTtosbOuBC4dz7uUeThBzprTjfFuVjc2t7Z3qbm1v/+DwyD4+6aookYR2SMQj2Q9AUc5C2tFMc9qPJQURcNoLZneF33uiUrEofNRpTH0Bk5CNGQFtpKF95s2oxpknQE+lyAhImeb50K47DWcOvE7cktRRifbQ/vFGEUkEDTXhoNTAdWLtZyA1I5zmNS9RNAYygwkdGBqCoMrP5vFzfGmUER5H0kyo8Vz9e5GBUCoVgdksYqpVrxD/8waJHjf9jIVxomlIFo/GCcc6wkUXeMQkJZqnhgCRzGTFZAoSiDaNLX0JJJieil7c1RbWSfe64ToN9+Gm3mqWDVXRObpAV8hFt6iF7lEbdRBBGXpBr+jNerberQ/rc7FascqbU7QE6+sXPQOegQ==AAACEXicbVDLSsNAFJ3UV62vqLhyM1gEVyURwS4LblxWsA9oQrmZTtuhM0mYmQgh5Cv8Arf6Be7ErV/gB/gfTtosbOuBC4dz7uUeThBzprTjfFuVjc2t7Z3qbm1v/+DwyD4+6aookYR2SMQj2Q9AUc5C2tFMc9qPJQURcNoLZneF33uiUrEofNRpTH0Bk5CNGQFtpKF95s2oxpknQE+lyAhImeb50K47DWcOvE7cktRRifbQ/vFGEUkEDTXhoNTAdWLtZyA1I5zmNS9RNAYygwkdGBqCoMrP5vFzfGmUER5H0kyo8Vz9e5GBUCoVgdksYqpVrxD/8waJHjf9jIVxomlIFo/GCcc6wkUXeMQkJZqnhgCRzGTFZAoSiDaNLX0JJJieil7c1RbWSfe64ToN9+Gm3mqWDVXRObpAV8hFt6iF7lEbdRBBGXpBr+jNerberQ/rc7FascqbU7QE6+sXPQOegQ==AAACEXicbVDLSsNAFJ3UV62vqLhyM1gEVyURwS4LblxWsA9oQrmZTtuhM0mYmQgh5Cv8Arf6Be7ErV/gB/gfTtosbOuBC4dz7uUeThBzprTjfFuVjc2t7Z3qbm1v/+DwyD4+6aookYR2SMQj2Q9AUc5C2tFMc9qPJQURcNoLZneF33uiUrEofNRpTH0Bk5CNGQFtpKF95s2oxpknQE+lyAhImeb50K47DWcOvE7cktRRifbQ/vFGEUkEDTXhoNTAdWLtZyA1I5zmNS9RNAYygwkdGBqCoMrP5vFzfGmUER5H0kyo8Vz9e5GBUCoVgdksYqpVrxD/8waJHjf9jIVxomlIFo/GCcc6wkUXeMQkJZqnhgCRzGTFZAoSiDaNLX0JJJieil7c1RbWSfe64ToN9+Gm3mqWDVXRObpAV8hFt6iF7lEbdRBBGXpBr+jNerberQ/rc7FascqbU7QE6+sXPQOegQ==

We will now explain this circuit and in the lab we will extend
this to a two bit adder.

MULT20015 Elements of Quantum Computing
Lecture 8

0 + 0 = 0

002=0

0 + 0 = 0
|0i

AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=AAACAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyKYI4BLx4jmAckS5id9CZjZmeXmVkhLLn4BV71C7yJV//ED/A/nCR7MIkFDUVVN91dQSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJS8epYthksYhVJ6AaBZfYNNwI7CQKaRQIbAfj25nffkKleSwfzCRBP6JDyUPOqLFSqzdGQ9x+ueJW3TnIOvFyUoEcjX75pzeIWRqhNExQrbuemxg/o8pwJnBa6qUaE8rGdIhdSyWNUPvZ/NopubDKgISxsiUNmat/JzIaaT2JAtsZUTPSq95M/M/rpias+RmXSWpQssWiMBXExGT2OhlwhcyIiSWUKW5vJWxEFWXGBrS0JVDUBjO1uXirKayT1lXVc6ve/XWlXssTKsIZnMMleHADdbiDBjSBwSO8wCu8Oc/Ou/PhfC5aC04+cwpLcL5+AYOhlvQ=

MULT20015 Elements of Quantum Computing
Lecture 8

0 + 1 = 1

012 = 1

|1i
AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=

0 + 1 = 1

MULT20015 Elements of Quantum Computing
Lecture 8

1 + 0 = 1

012 = 1

1 + 0 = 1

MULT20015 Elements of Quantum Computing
Lecture 8

1 + 1 = 2

102 = 2

1 + 1 = 2
|1i

AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=

MULT20015 Elements of Quantum Computing
Lecture 8

1+1 Quantum Style

Here is what happens when we add together numbers in superposition:

|0i+ |1i
p
2

AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVWMXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVWMXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVWMXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVWMXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=

“+” |1iAAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=AAACAXicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEsMeCF48VbCu0oWy2m3bJZhN2J0IJPfkLvOov8CZe/SX+AP+H2zYH2/pg4PHeDDPzglQKg6777ZQ2Nre2d8q7lb39g8Oj6vFJxySZZrzNEpnox4AaLoXibRQo+WOqOY0DybtBdDvzu09cG5GoB5yk3I/pSIlQMIpW6vYjjsQjg2rNrbtzkHXiFaQGBVqD6k9/mLAs5gqZpMb0PDdFP6caBZN8WulnhqeURXTEe5YqGnPj5/Nzp+TCKkMSJtqWQjJX/07kNDZmEge2M6Y4NqveTPzP62UYNvxcqDRDrthiUZhJggmZ/U6GQnOGcmIJZVrYWwkbU00Z2oSWtgSa2mSmNhdvNYV10rmqe27du7+uNRtFQmU4g3O4BA9uoAl30II2MIjgBV7hzXl23p0P53PRWnKKmVNYgvP1C98Klx8=

|0i+ |1i
p
2

Let’s do the walkthrough…

MULT20015 Elements of Quantum Computing
Lecture 8

One Qubit adder – example

|0i+ |1i
p
2

| i =
|0i+ |1i

p
2

⌦ |1i ⌦ |0i ⌦ |0i
AAACVXicbZDLSsNAFIansWqtl0ZduhksgiCUpAh2IxTcuKxgL9KEMplO2qGTizMnQgl5Nh9DfIBu9QkEp2kWtvXAwH/+/xzO8Hmx4Aos67Nk7JR39/YrB9XDo+OTmnl61lNRIinr0khEcuARxQQPWRc4CDaIJSOBJ1jfmz0s8/4bk4pH4TPMY+YGZBJyn1MC2hqZL86MAXZixfE9dnxJaJo7Fr7BubCz1FGvEtJmlmEnAh4wVSTrrbXRjsy61bDywtvCLkQdFdUZmQtnHNEkYCFQQZQa2lYMbkokcCpYVnUSxWJCZ2TChlqGRN9y0xxBhq+0M8Z+JPULAefu342UBErNA09PBgSmajNbmv9lwwT8lpvyME6AhXR1yE8EhggveeIxl4yCmGtBqOT6r5hOieYImvraFU8SDSbTXOxNCtui12zYVsN+uq23WwWhCrpAl+ga2egOtdEj6qAuougdLdAX+i59lH6MsrG3GjVKxc45Wiuj9gv3B7Q3AAACVXicbZDLSsNAFIansWqtl0ZduhksgiCUpAh2IxTcuKxgL9KEMplO2qGTizMnQgl5Nh9DfIBu9QkEp2kWtvXAwH/+/xzO8Hmx4Aos67Nk7JR39/YrB9XDo+OTmnl61lNRIinr0khEcuARxQQPWRc4CDaIJSOBJ1jfmz0s8/4bk4pH4TPMY+YGZBJyn1MC2hqZL86MAXZixfE9dnxJaJo7Fr7BubCz1FGvEtJmlmEnAh4wVSTrrbXRjsy61bDywtvCLkQdFdUZmQtnHNEkYCFQQZQa2lYMbkokcCpYVnUSxWJCZ2TChlqGRN9y0xxBhq+0M8Z+JPULAefu342UBErNA09PBgSmajNbmv9lwwT8lpvyME6AhXR1yE8EhggveeIxl4yCmGtBqOT6r5hOieYImvraFU8SDSbTXOxNCtui12zYVsN+uq23WwWhCrpAl+ga2egOtdEj6qAuougdLdAX+i59lH6MsrG3GjVKxc45Wiuj9gv3B7Q3AAACVXicbZDLSsNAFIansWqtl0ZduhksgiCUpAh2IxTcuKxgL9KEMplO2qGTizMnQgl5Nh9DfIBu9QkEp2kWtvXAwH/+/xzO8Hmx4Aos67Nk7JR39/YrB9XDo+OTmnl61lNRIinr0khEcuARxQQPWRc4CDaIJSOBJ1jfmz0s8/4bk4pH4TPMY+YGZBJyn1MC2hqZL86MAXZixfE9dnxJaJo7Fr7BubCz1FGvEtJmlmEnAh4wVSTrrbXRjsy61bDywtvCLkQdFdUZmQtnHNEkYCFQQZQa2lYMbkokcCpYVnUSxWJCZ2TChlqGRN9y0xxBhq+0M8Z+JPULAefu342UBErNA09PBgSmajNbmv9lwwT8lpvyME6AhXR1yE8EhggveeIxl4yCmGtBqOT6r5hOieYImvraFU8SDSbTXOxNCtui12zYVsN+uq23WwWhCrpAl+ga2egOtdEj6qAuougdLdAX+i59lH6MsrG3GjVKxc45Wiuj9gv3B7Q3AAACVXicbZDLSsNAFIansWqtl0ZduhksgiCUpAh2IxTcuKxgL9KEMplO2qGTizMnQgl5Nh9DfIBu9QkEp2kWtvXAwH/+/xzO8Hmx4Aos67Nk7JR39/YrB9XDo+OTmnl61lNRIinr0khEcuARxQQPWRc4CDaIJSOBJ1jfmz0s8/4bk4pH4TPMY+YGZBJyn1MC2hqZL86MAXZixfE9dnxJaJo7Fr7BubCz1FGvEtJmlmEnAh4wVSTrrbXRjsy61bDywtvCLkQdFdUZmQtnHNEkYCFQQZQa2lYMbkokcCpYVnUSxWJCZ2TChlqGRN9y0xxBhq+0M8Z+JPULAefu342UBErNA09PBgSmajNbmv9lwwT8lpvyME6AhXR1yE8EhggveeIxl4yCmGtBqOT6r5hOieYImvraFU8SDSbTXOxNCtui12zYVsN+uq23WwWhCrpAl+ga2egOtdEj6qAuougdLdAX+i59lH6MsrG3GjVKxc45Wiuj9gv3B7Q3

MULT20015 Elements of Quantum Computing
Lecture 8

One Qubit adder – example

|0i+ |1i
p
2

| i =
|0i+ |1i

p
2

flip

no flip

| i =
|0100i+ |1101i

p
2

AAACL3icbZDLSgMxFIYzXmu9VV26CRZBEEriBd0IBTcuK9ha6JSSSTNtaOZickYowzyIj+ETuNUnEDfixoVvYTrtwrb+EPj5zzmck8+LlTRAyIezsLi0vLJaWCuub2xubZd2dhsmSjQXdR6pSDc9ZoSSoaiDBCWasRYs8JS49wbXo/r9o9BGRuEdDGPRDlgvlL7kDGzUKZ26AwGpGxuZ4Svs+prxNI8IJSQ7zi2lhGZZ6poHDelJlnVKZVIhufC8oRNTRhPVOqVvtxvxJBAhcMWMaVESQztlGiRXIiu6iREx4wPWEy1rQxYI007zz2X40CZd7EfavhBwnv6dSFlgzDDwbGfAoG9ma6Pwv1orAf+yncowTkCEfLzITxSGCI9I4a7UgoMaWsO4lvZWzPvMAgLLc2qLp5nlNOJCZynMm8ZJhZ5Wzm/PytXLCaEC2kcH6AhRdIGq6AbVUB1x9IRe0Ct6c56dd+fT+Rq3LjiTmT00JefnFzctqdI=

MULT20015 Elements of Quantum Computing
Lecture 8

One Qubit adder – example

|0i+ |1i
p
2

| i =
|0i+ |1i

p
2

flip flip

| i =
|0100i+ |1101i

p
2

| i =
|0101i+ |1100i

p
2

AAACL3icbZDLSgMxFIYzXmu9VV26CRZBEEriBd0IBTcuK9ha6JSSSTNtaOZickYowzyIj+ETuNUnEDfixoVvYTrtwrb+EPj5zzmck8+LlTRAyIezsLi0vLJaWCuub2xubZd2dhsmSjQXdR6pSDc9ZoSSoaiDBCWasRYs8JS49wbXo/r9o9BGRuEdDGPRDlgvlL7kDGzUKZ26AwGpGxuZ4Svs+prxNI8IJTQ7zi2lhGRZ6poHDelJlnVKZVIhufC8oRNTRhPVOqVvtxvxJBAhcMWMaVESQztlGiRXIiu6iREx4wPWEy1rQxYI007zz2X40CZd7EfavhBwnv6dSFlgzDDwbGfAoG9ma6Pwv1orAf+yncowTkCEfLzITxSGCI9I4a7UgoMaWsO4lvZWzPvMAgLLc2qLp5nlNOJCZynMm8ZJhZ5Wzm/PytXLCaEC2kcH6AhRdIGq6AbVUB1x9IRe0Ct6c56dd+fT+Rq3LjiTmT00JefnFzc4qdI=

MULT20015 Elements of Quantum Computing
Lecture 8

| i =
|0101i+ |1100i

p
2

AAACL3icbZDLSgMxFIYzXmu9VV26CRZBEEriBd0IBTcuK9ha6JSSSTNtaOZickYowzyIj+ETuNUnEDfixoVvYTrtwrb+EPj5zzmck8+LlTRAyIezsLi0vLJaWCuub2xubZd2dhsmSjQXdR6pSDc9ZoSSoaiDBCWasRYs8JS49wbXo/r9o9BGRuEdDGPRDlgvlL7kDGzUKZ26AwGpGxuZ4Svs+prxNI8IJTQ7zi2lhGRZ6poHDelJlnVKZVIhufC8oRNTRhPVOqVvtxvxJBAhcMWMaVESQztlGiRXIiu6iREx4wPWEy1rQxYI007zz2X40CZd7EfavhBwnv6dSFlgzDDwbGfAoG9ma6Pwv1orAf+yncowTkCEfLzITxSGCI9I4a7UgoMaWsO4lvZWzPvMAgLLc2qLp5nlNOJCZynMm8ZJhZ5Wzm/PytXLCaEC2kcH6AhRdIGq6AbVUB1x9IRe0Ct6c56dd+fT+Rq3LjiTmT00JefnFzc4qdI=

One Qubit adder – example

|0i+ |1i
p
2

| i =
|0i+ |1i

p
2

no flip

flip

| i =
|0100i+ |1101i

p
2

| i =
|0101i+ |1110i

p
2

AAACL3icbZDLSgMxFIYz9VbrrerSTbAIglAmrWI3QsGNywq2FjqlZNJMG5q5mJwRyjAP4mP4BG71CcSNuHHhW5hOu7CtPwR+/nMO5+RzIyk02PaHlVtZXVvfyG8WtrZ3dveK+wctHcaK8SYLZajaLtVcioA3QYDk7Uhx6ruS37uj60n9/pErLcLgDsYR7/p0EAhPMAom6hWrzohD4kRapPgKO56iLMkim9gkPcssIcRO08TRDwqSSpr2iiW7bGfCy4bMTAnN1OgVv51+yGKfB8Ak1bpD7Ai6CVUgmORpwYk1jygb0QHvGBtQn+tukn0uxScm6WMvVOYFgLP070RCfa3Hvms6fQpDvVibhP/VOjF4tW4igigGHrDpIi+WGEI8IYX7QnEGcmwMZUqYWzEbUgMIDM+5La6ihtOEC1mksGxalTKpli9uz0v12oxQHh2hY3SKCLpEdXSDGqiJGHpCL+gVvVnP1rv1aX1NW3PWbOYQzcn6+QU43KnT

MULT20015 Elements of Quantum Computing
Lecture 8

One Qubit adder – example

|0i+ |1i
p
2

AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVW MXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVW MXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVW MXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=AAACHXicbZDLSsNAFIYn9VbrLerSzWgRBKEkRbDLghuXFewFmlAm00k7dHJx5kQoIWsfwydwq0/gTtyKD+B7OGmzsK0/DPz85xzOmc+LBVdgWd9GaW19Y3OrvF3Z2d3bPzAPjzoqSiRlbRqJSPY8opjgIWsDB8F6sWQk8ATrepObvN59ZFLxKLyHaczcgIxC7nNKQEcD89TxJaGpM2GALXyJZ8bGWeqoBwlpPcsGZtWqWTPhVW MXpooKtQbmjzOMaBKwEKggSvVtKwY3JRI4FSyrOIliMaETMmJ9bUMSMOWms69k+FwnQ+xHUr8Q8Cz9O5GSQKlp4OnOgMBYLdfy8L9aPwG/4aY8jBNgIZ0v8hOBIcI5FzzkklEQU20IlVzfiumYaDag6S1s8STRkHIu9jKFVdOp12yrZt9dVZuNglAZnaAzdIFsdI2a6Ba1UBtR9IRe0Ct6M56Nd+PD+Jy3loxi5hgtyPj6BQdJoec=

Or, considering the last two registers as a two-qubit register (binary notation):

0+1=1 1+1=2

Note: this is an
entangled state.| i =

|0i |1i |1i+ |1i |1i |2i
p
2

AAACRXicbZBLSwMxEMez9VXrq+rRS7AIglB2i2AvQsGL3irYB3SXkk2zbWj2YTIrlGU/kx/DT+DBi548ehOvmt1WsK0DYf75zwyT/NxIcAWm+WIUVlbX1jeKm6Wt7Z3dvfL+QVuFsaSsRUMRyq5LFBM8YC3gIFg3koz4rmAdd3yV1TsPTCoeBncwiZjjk2HAPU4JaKtfvrHHDLAdKY4vse1JQhOcW+Y0Wb/pbOGep1qa2OpeQlJL0365YlbNPPCysGaigmbR7Jff7UFIY58FQAVRqmeZETgJkcCpYGnJjhWLCB2TIetpGRCfKSfJv5ziE+0MsBdKfQLAuft3IiG+UhPf1Z0+gZFarGXmf7VeDF7dSXgQxcACOl3kxQJDiDN+eMAloyAmWhAquX4rpiOiuYGmPLfFlUQzyrhYixSWRbtWtcyqdXteadRnhIroCB2jU2ShC9RA16iJWoiiR/SMXtGb8WR8GJ/G17S1YMxmDtFcGN8/zmevoQ==AAACRXicbZBLSwMxEMez9VXrq+rRS7AIglB2i2AvQsGL3irYB3SXkk2zbWj2YTIrlGU/kx/DT+DBi548ehOvmt1WsK0DYf75zwyT/NxIcAWm+WIUVlbX1jeKm6Wt7Z3dvfL+QVuFsaSsRUMRyq5LFBM8YC3gIFg3koz4rmAdd3yV1TsPTCoeBncwiZjjk2HAPU4JaKtfvrHHDLAdKY4vse1JQhOcW+Y0Wb/pbOGep1qa2OpeQlJL0365YlbNPPCysGaigmbR7Jff7UFIY58FQAVRqmeZETgJkcCpYGnJjhWLCB2TIetpGRCfKSfJv5ziE+0MsBdKfQLAuft3IiG+UhPf1Z0+gZFarGXmf7VeDF7dSXgQxcACOl3kxQJDiDN+eMAloyAmWhAquX4rpiOiuYGmPLfFlUQzyrhYixSWRbtWtcyqdXteadRnhIroCB2jU2ShC9RA16iJWoiiR/SMXtGb8WR8GJ/G17S1YMxmDtFcGN8/zmevoQ==AAACRXicbZBLSwMxEMez9VXrq+rRS7AIglB2i2AvQsGL3irYB3SXkk2zbWj2YTIrlGU/kx/DT+DBi548ehOvmt1WsK0DYf75zwyT/NxIcAWm+WIUVlbX1jeKm6Wt7Z3dvfL+QVuFsaSsRUMRyq5LFBM8YC3gIFg3koz4rmAdd3yV1TsPTCoeBncwiZjjk2HAPU4JaKtfvrHHDLAdKY4vse1JQhOcW+Y0Wb/pbOGep1qa2OpeQlJL0365YlbNPPCysGaigmbR7Jff7UFIY58FQAVRqmeZETgJkcCpYGnJjhWLCB2TIetpGRCfKSfJv5ziE+0MsBdKfQLAuft3IiG+UhPf1Z0+gZFarGXmf7VeDF7dSXgQxcACOl3kxQJDiDN+eMAloyAmWhAquX4rpiOiuYGmPLfFlUQzyrhYixSWRbtWtcyqdXteadRnhIroCB2jU2ShC9RA16iJWoiiR/SMXtGb8WR8GJ/G17S1YMxmDtFcGN8/zmevoQ==AAACRXicbZBLSwMxEMez9VXrq+rRS7AIglB2i2AvQsGL3irYB3SXkk2zbWj2YTIrlGU/kx/DT+DBi548ehOvmt1WsK0DYf75zwyT/NxIcAWm+WIUVlbX1jeKm6Wt7Z3dvfL+QVuFsaSsRUMRyq5LFBM8YC3gIFg3koz4rmAdd3yV1TsPTCoeBncwiZjjk2HAPU4JaKtfvrHHDLAdKY4vse1JQhOcW+Y0Wb/pbOGep1qa2OpeQlJL0365YlbNPPCysGaigmbR7Jff7UFIY58FQAVRqmeZETgJkcCpYGnJjhWLCB2TIetpGRCfKSfJv5ziE+0MsBdKfQLAuft3IiG+UhPf1Z0+gZFarGXmf7VeDF7dSXgQxcACOl3kxQJDiDN+eMAloyAmWhAquX4rpiOiuYGmPLfFlUQzyrhYixSWRbtWtcyqdXteadRnhIroCB2jU2ShC9RA16iJWoiiR/SMXtGb8WR8GJ/G17S1YMxmDtFcGN8/zmevoQ==

| i =
|0101i+ |1110i

p
2

| i =
|0101i+ |1110i

p
2

MULT20015 Elements of Quantum Computing
Lecture 8

Implementing irreversible functions

We cannot compute irreversible functions directly (not unitary). One strategy
which you often see to make an irreversible function reversible is simply to
propagate the input to the output:

Uf
|0i

|f(x)i
AAACBHicbVDLSsNAFJ34rPVVdekmWIS6KYkIdllw47KCfWAbymR60w6dTMLMjVhCt36BW/0Cd+LW//AD/A8nbRa29cCFwzn3cu89fiy4Rsf5ttbWNza3tgs7xd29/YPD0tFxS0eJYtBkkYhUx6caBJfQRI4COrECGvoC2v74JvPbj6A0j+Q9TmLwQjqUPOCMopEeemPANKg8XUz7pbJTdWawV4mbkzLJ0eiXfnqDiCUhSGSCat11nRi9lCrkTMC02Es0xJSN6RC6hkoagvbS2cVT+9woAzuIlCmJ9kz9O5HSUOtJ6JvOkOJIL3uZ+J/XTTCoeSmXcYIg2XxRkAgbIzt73x5wBQzFxBDKFDe32mxEFWVoQlrY4itqwslycZdTWCWty6rrVN27q3K9lidUIKfkjFSIS65JndySBmkSRiR5Ia/kzXq23q0P63PeumblMydkAdbXLxCumPM=AAACBHicbVDLSsNAFJ34rPVVdekmWIS6KYkIdllw47KCfWAbymR60w6dTMLMjVhCt36BW/0Cd+LW//AD/A8nbRa29cCFwzn3cu89fiy4Rsf5ttbWNza3tgs7xd29/YPD0tFxS0eJYtBkkYhUx6caBJfQRI4COrECGvoC2v74JvPbj6A0j+Q9TmLwQjqUPOCMopEeemPANKg8XUz7pbJTdWawV4mbkzLJ0eiXfnqDiCUhSGSCat11nRi9lCrkTMC02Es0xJSN6RC6hkoagvbS2cVT+9woAzuIlCmJ9kz9O5HSUOtJ6JvOkOJIL3uZ+J/XTTCoeSmXcYIg2XxRkAgbIzt73x5wBQzFxBDKFDe32mxEFWVoQlrY4itqwslycZdTWCWty6rrVN27q3K9lidUIKfkjFSIS65JndySBmkSRiR5Ia/kzXq23q0P63PeumblMydkAdbXLxCumPM=AAACBHicbVDLSsNAFJ34rPVVdekmWIS6KYkIdllw47KCfWAbymR60w6dTMLMjVhCt36BW/0Cd+LW//AD/A8nbRa29cCFwzn3cu89fiy4Rsf5ttbWNza3tgs7xd29/YPD0tFxS0eJYtBkkYhUx6caBJfQRI4COrECGvoC2v74JvPbj6A0j+Q9TmLwQjqUPOCMopEeemPANKg8XUz7pbJTdWawV4mbkzLJ0eiXfnqDiCUhSGSCat11nRi9lCrkTMC02Es0xJSN6RC6hkoagvbS2cVT+9woAzuIlCmJ9kz9O5HSUOtJ6JvOkOJIL3uZ+J/XTTCoeSmXcYIg2XxRkAgbIzt73x5wBQzFxBDKFDe32mxEFWVoQlrY4itqwslycZdTWCWty6rrVN27q3K9lidUIKfkjFSIS65JndySBmkSRiR5Ia/kzXq23q0P63PeumblMydkAdbXLxCumPM=AAACBHicbVDLSsNAFJ34rPVVdekmWIS6KYkIdllw47KCfWAbymR60w6dTMLMjVhCt36BW/0Cd+LW//AD/A8nbRa29cCFwzn3cu89fiy4Rsf5ttbWNza3tgs7xd29/YPD0tFxS0eJYtBkkYhUx6caBJfQRI4COrECGvoC2v74JvPbj6A0j+Q9TmLwQjqUPOCMopEeemPANKg8XUz7pbJTdWawV4mbkzLJ0eiXfnqDiCUhSGSCat11nRi9lCrkTMC02Es0xJSN6RC6hkoagvbS2cVT+9woAzuIlCmJ9kz9O5HSUOtJ6JvOkOJIL3uZ+J/XTTCoeSmXcYIg2XxRkAgbIzt73x5wBQzFxBDKFDe32mxEFWVoQlrY4itqwslycZdTWCWty6rrVN27q3K9lidUIKfkjFSIS65JndySBmkSRiR5Ia/kzXq23q0P63PeumblMydkAdbXLxCumPM=

Propagate
inputs to
output

Calculated f(x)

MULT20015 Elements of Quantum Computing
Lecture 8

One Bit Adder

The adder is an example. Given a + b, we can’t uniquely determine a and b
So we used this trick:

Propagated
inputs to
output

Evaluated function

MULT20015 Elements of Quantum Computing
Lecture 8

8.4 Universality in Quantum Computing

MULT20015
Lecture 8

MULT20015 Elements of Quantum Computing
Lecture 8

Universality

In classical computing the NAND gate is universal, i.e. every Boolean function can be
implemented as a sequence of NAND (NOT AND) gates:

In quantum computing every quantum circuit can be expressed as a sequence of:

CNOT

hXi

hY i

hZi

|0i

|1i

Single Qubit Rotations

MULT20015 Elements of Quantum Computing
Lecture 8

Universality

In classical computing the NAND gate is universal, i.e. every Boolean function can be
implemented as a sequence of NAND (NOT AND) gates:

In quantum computing every quantum circuit can be expressed as a sequence of:

CNOT Hadamard

H T

T Gate
(pi/8)

MULT20015 Elements of Quantum Computing
Lecture 8

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/5 – Multi-qubit states and quantum arithmetic
5/6 – Classical complexity and simple quantum algorithms
6/7 – 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

Related Posts