The Ripple Carry Adder quantum kata is a series of exercises designed to get you familiar with ripple carry addition on a quantum computer.
using the same basic components and the same algorithm.
to reduce the number of ancillary qubits needed.
It is recommended to complete the BasicGates kata before this one to get familiar with the basic gates used in quantum computing. The list of basic gates available in Q# can be found at Microsoft.Quantum.Intrinsic. For the syntax of flow control statements in Q#, see Q# iterations and Q# conditional branching documentation.
Each task is wrapped in one operation preceded by the description of the task. Your goal is to fill in the blank (marked with // ... comments) with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
Within each section, tasks are given in approximate order of increasing difficulty; harder ones are marked with asterisks.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,sum
in state $|0\rangle$.Goal: Transform the sum
qubit into the lowest bit of the binary sum of $\phi$ and $\psi$.
Any superposition should map appropriately.
Example: (Recall that $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$)
$|+\rangle \otimes |-\rangle \otimes |0\rangle \to \frac{1}{2}(|000\rangle + |101\rangle - |011\rangle - |110\rangle)$
%kata T11_LowestBitSum
operation LowestBitSum (a : Qubit, b : Qubit, sum : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goal: Set the carry
qubit to $|1\rangle$ if the binary sum of $\phi$ and $\psi$ produces a carry.
Any superposition should map appropriately.
Example:
$|+\rangle \otimes |-\rangle \otimes |0\rangle \to \frac{1}{2}(|000\rangle + |100\rangle - |010\rangle - |111\rangle)$
%kata T12_LowestBitCarry
operation LowestBitCarry (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in the Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,sum
and carry
in state $|0\rangle$.Goals:
sum
qubit into the lowest bit of the binary sum of $\phi$ and $\psi$.carry
qubit into the carry bit produced by that sum.%kata T13_OneBitAdder
operation OneBitAdder (a : Qubit, b : Qubit, sum : Qubit, carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in the Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carryin
in an arbitrary state $|\omega\rangle$,sum
in state $|0\rangle$.Goal: Transform the sum
qubit into the lowest bit of the binary sum of $\phi$, $\psi$ and $\omega$.
%kata T14_HighBitSum
operation HighBitSum (a : Qubit, b : Qubit, carryin : Qubit, sum : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carryin
in an arbitrary state $|\omega\rangle$,carryout
in state $|0\rangle$.Goal: Transform the carryout
qubit into the carry bit produced by the sum of $\phi$, $\psi$ and $\omega$.
%kata T15_HighBitCarry
operation HighBitCarry (a : Qubit, b : Qubit, carryin : Qubit, carryout : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,sum
in state $|00\rangle$,carry
in state $|0\rangle$.Goals:
sum
register into the binary sum (little-endian) of $\phi$ and $\psi$.carry
qubit into the carry bit produced by that sum.All registers in this kata are in little-endian order. This means that they have the least significant bit first, followed by the next least significant, and so on.
In this exercise, for example, $1$ would be represented as $|10\rangle$, and $2$ as $|01\rangle$.
The sum of $|10\rangle$ and $|11\rangle$ would be $|001\rangle$, with the last qubit being the carry qubit.
%kata T16_TwoBitAdder
operation TwoBitAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,sum
in state $|0...0\rangle$,carry
in state $|0\rangle$.Goals:
sum
register into the binary sum (little-endian) of $\phi$ and $\psi$.carry
qubit into the carry bit produced by that sum.Challenge:
Can you do this without allocating extra qubits?
%kata T17_ArbitraryAdder
operation ArbitraryAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
The adder from the previous section requires empty qubits to accept the result. This section adapts the previous adder to calculate the sum in-place, that is, to reuse one of the numerical inputs for storing the output.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$.Goals:
b
into the lowest bit of the sum of $\phi$ and $\psi$.a
unchanged.%kata T21_LowestBitSumInPlace
operation LowestBitSumInPlace (a : Qubit, b : Qubit) : Unit is Adj {
// ...
}
Can we re-use one of the input bits to calculate the carry in-place as well? Why or why not?
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goals:
carry
qubit into the carry bit from the addition of $\phi$ and $\psi$.b
into the lowest bit of $\phi + \psi$.a
unchanged.%kata T22_OneBitAdderInPlace
operation OneBitAdderInPlace (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carryin
in an arbitrary state $|\omega\rangle$.Goals:
b
into the lowest bit from the sum $\phi + \psi + \omega$.a
and carryin
unchanged.%kata T23_HighBitSumInPlace
operation HighBitSumInPlace (a : Qubit, b : Qubit, carryin : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goals:
b
into the state $|\phi + \psi\rangle$.carry
qubit into the carry bit from the addition.a
unchanged.%kata T24_TwoBitAdderInPlace
operation TwoBitAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goals:
b
into the state $|\phi + \psi\rangle$.carry
qubit into the carry bit from the addition.a
unchanged.%kata T25_ArbitraryAdderInPlace
operation ArbitraryAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in Ripple Carry Adder Workbook.
The in-place adder doesn't require quite as many qubits for the inputs and outputs, but it still requires an array of extra ("ancillary") qubits to perform the calculation.
A relatively recent algorithm allows you to perform the same calculation using only one additional qubit.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,c
in an arbitrary state $|\omega\rangle$.Goal: Construct the "in-place majority" gate:
a
into the carry bit from the sum $\phi + \psi + \omega$.b
into $|\phi + \psi\rangle$.c
into $|\phi + \omega\rangle$.%kata T31_Majority
operation Majority (a : Qubit, b : Qubit, c : Qubit) : Unit is Adj {
// ...
}
Inputs:
a
storing the carry bit from the sum $\phi + \psi + \omega$,b
in state $|\phi + \psi\rangle$,c
in state $|\phi + \omega\rangle$.Goal: Construct the "un-majority and add", or "UMA" gate:
a
into state $|\phi\rangle$.b
into state $|\phi + \psi + \omega\rangle$.c
into state $|\omega\rangle$.%kata T32_UnMajorityAdd
operation UnMajorityAdd (a : Qubit, b : Qubit, c : Qubit) : Unit is Adj {
// ...
}
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goal: Construct a one-bit binary adder from task 2.2 using Majority and UMA gates.
%kata T33_OneBitMajUmaAdder
operation OneBitMajUmaAdder (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {
// ...
}
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goal: Construct a two-bit binary adder from task 2.4 using Majority and UMA gates.
%kata T34_TwoBitMajUmaAdder
operation TwoBitMajUmaAdder (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {
// ...
}
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,carry
in state $|0\rangle$.Goal: Construct an N-bit binary adder from task 2.5 using only one ancillary qubit.
%kata T35_ArbitraryMajUmaAdder
operation ArbitraryMajUmaAdder (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {
// ...
}
Subtracting a number is the same operation as adding a negative number. As such, it's pretty easy to adapt the adder we just built to act as a subtractor.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,borrowBit
in state $|0\rangle$.Goal: Construct an N-bit binary subtractor.
b
into the state $|\psi - \phi\rangle$.borrowBit
to $|1\rangle$ if that subtraction requires a borrow.a
unchanged.%kata T41_Subtractor
operation Subtractor (a : Qubit[], b : Qubit[], borrowBit : Qubit) : Unit is Adj {
// ...
}
In the previous parts we considered "normal" arithmetic, in which the sum of two numbers can have more bits than each of the summands. In these tasks we have used an extra qubit to store the "carry" or "borrow" bit (the most significant bit). If we want to perform our computation modulo $2^N$ instead, in classical computing we can easily discard this "carry" qubit and get the result modulo $2^N$ automatically. However, in quantum computing information cannot be erased that easily: this extra qubit is changed after the operation, and "discarding" it can affect the state of the other qubits. We need to modify the computation itself so that the last carry qubit is not involved at all. In this part we will learn to implement operations modulo $2^N$ which do either not use this extra qubit or uncompute it after use.
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,sum
in the state $|0...0\rangle$.Goal:
Transform the register sum
into the state $|(\phi + \psi) \mod 2^N\rangle$.
Leave registers a
and b
unchanged.
%kata T51_AdderModuloN
operation AdderModuloN (a : Qubit[], b : Qubit[], sum : Qubit[]) : Unit is Adj {
// ...
}
Input:
$N$-qubit register a
in an arbitrary state $|\phi\rangle$.
Goal: Transform the register a
into two's complement of $\phi$.
%kata T52_TwosComplement
operation TwosComplement (a : Qubit[]) : Unit is Adj {
// ...
}
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$,diff
in the state $|0...0\rangle$.Goal: transform the register diff
into the state $|(\psi - \phi) \mod 2^N\rangle$.
Leave registers a
and b
unchanged.
%kata T53_SubtractorModuloN
operation SubtractorModuloN (a : Qubit[], b : Qubit[], diff : Qubit[]) : Unit is Adj {
// ...
}
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$.Goal: Transform the register b
into the state $|(\phi + \psi) \mod 2^N\rangle$.
Leave register a
unchanged.
%kata T54_InPlaceAdderModuloN
operation InPlaceAdderModuloN (a : Qubit[], b : Qubit[]) : Unit is Adj {
// ...
}
Inputs:
a
in an arbitrary state $|\phi\rangle$,b
in an arbitrary state $|\psi\rangle$.Goal: Transform the register b
into the state $|(\psi - \phi) \mod 2^N\rangle$.
Leave register a
unchanged.
%kata T55_InPlaceSubtractorModuloN
operation InPlaceSubtractorModuloN (a : Qubit[], b : Qubit[]) : Unit is Adj {
// ...
}