Toffoli Gate

QSharp

On this page:

The Toffoli Gate
Syntax
1 and 2 Qubit Registers
3 Qubit Register
3 Qubit (and larger) Registers
The Column Method

The Toffoli Gate

The TOFFOLI gate acts on three qubits. It flips the target qubit if and only if both control qubits are 1. The TOFFOLI gate is a doubly-controlled NOT gate. The TOFFOLI gate is represented by the following matrix:

The Toffoli matrix

//	One-line notation (too long for one line really)
{{1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 1, 0}}

//	Expanded notation (and a good example of why performing these calculations manually is time fiddly!)
{
{1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 0}
}

Manipulation of a register takes the form of matrix algebra. In order for the mathematics to take place, matricies of appropriate size must be constructed. This can be a tedious and time consuming process.

Thankfully, there is an easier way to compute these outcomes, as will be demonstrated.

It is not possible to 'step-up' a TOFFOLI gate to an appropriate size via the same method used for the single-qubit family of matrices (Pauli, Hadamard etc.). Instead, X and I matrices are combined and tensored together in various ways to achieve the desired result. This process is counter-intuitive and difficult to work out manually, and becomes almost impossible when more than 6 or 7 qubits are involved. The following examples will demonstrate this, and will demonstrate why the Column Method is superior for these complex calculations.

Syntax

The Quantum Console syntax for this operation is:

TOFFOLI(Control0_n, Control1_n, Target_n);

Where Control0_n and Control1_n specifies the indices of the control qubits, and Target_n specifies the qubit we wish to manipulate.

* Note that this index is 0 based, not 1 based as represented in most examples.

1 and 2 Qubit Registers

As the TOFFOLI gate operates on two qubits, it cannot be used with a single qubit register.

3 Qubit Register

Performing this calculation on a three qubit system is fairly straight forward, as the rules for matrix multiplication (number of columns from matrix A must match the number of rows from matrix B) are satisfied.

Matrix mathematics

For the operation TOFFOLI(0, 1, 2):

{
{1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 0}
}

{
{ACE|000›},
{ACF|001›},
{ADE|010›},
{ADF|011›},
{BCE|100›},
{BCF|101›},
{BDE|110›},
{BDF|111›}
}

{
{(1 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (1 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (1 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (1 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (1 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (1 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (1 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (1 * BDE|110›), (0 * BDF|111›)}
}

{
{ACE|000›},
{ACF|001›},
{ADE|010›},
{ADF|011›},
{BCE|100›},
{BCF|101›},
{BDF|111›},
{BDE|110›}
}

For the operation TOFFOLI(0, 2, 1):

{
{1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 0}
}

{
{ACE|000›},
{ACF|001›},
{ADE|010›},
{ADF|011›},
{BCE|100›},
{BCF|101›},
{BDE|110›},
{BDF|111›}
}

{
{(1 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (1 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (1 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (1 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (1 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (0 * BDE|110›), (1 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (0 * BCF|101›), (1 * BDE|110›), (0 * BDF|111›)},
{(0 * ACE|000›), (0 * ACF|001›), (0 * ADE|010›), (0 * ADF|011›), (0 * BCE|100›), (1 * BCF|101›), (0 * BDE|110›), (0 * BDF|111›)}
}

{
{ACE|000›},
{ACF|001›},
{ADE|010›},
{ADF|011›},
{BCE|100›},
{BDF|111›},
{BDE|110›},
{BCF|101›}
}

Performing the operation in Quantum Console

For the operation TOFFOLI(0, 1, 2):

//	Qubits
(A|0› + B|1›) (x) (C|0› + D|1›) (x) (E|0› + F|1›)

//	Computational Basis States - Input
ACE|000› + ACF|001› + ADE|010› + ADF|011› + BCE|100› + BCF|101› + BDE|110› + BDF|111›

//	Quantum Console syntax
//	Apply TOFFOLI using control qubits 0 and 1, and the target qubit 2
TOFFOLI(0, 1, 2);

//	Computational Basis States - Ouput
ACE|000› + ACF|001› + ADE|010› + ADF|011› + BCE|100› + BCF|101› + BDF|110› + BDE|111›

For the operation TOFFOLI(0, 2, 1):

//	Qubits
(A|0› + B|1›) (x) (C|0› + D|1›) (x) (E|0› + F|1›)

//	Computational Basis States - Input
ACE|000› + ACF|001› + ADE|010› + ADF|011› + BCE|100› + BCF|101› + BDE|110› + BDF|111›

//	Quantum Console syntax
//	Apply TOFFOLI using control qubits 0 and 2, and the target qubit 1
TOFFOLI(0, 2, 1);

//	Computational Basis States - Ouput
ACE|000› + ACF|001› + ADE|010› + ADF|011› + BCE|100› + BDF|101› + BDE|110› + BCF|111›

3 Qubit (and larger) Registers

This time, the state vector is larger again (2ⁿ, n = 3), at 8 rows, and due to this a TOFFOLI gate cannot be applied as the number of columns from matrix A (2) does not match the number of rows from matrix B (8).

Using the Pauli family of matrices, normally a matrix produced from the tensor products of X and I matrices would be constructed to perform the appropriate manipulation, however this method simply doesn't work for TOFFOLI operations.

Instead, we will go directly to the Column Method to perform the calculations manually.

The Column Method

You might find that using the column method is easier and faster - it took a while for me to develop, but now I find it easier to use than other methods.

To use the column method:

Write the state vector vertically down the page
Write an index over each bit column
Write the gate over the bit to be operated on
Now, work out the result of the operation, one element at a time, and write these into a new column

TOFFOLI 3 Qubit Example

Applying the column method to the 3 qubit example from above:

//	TOFFOLI(0, 1, 2);
//	Apply the TOFFOLI gate, one element at a time
//	C denotes the control qubit
//	T denotes the target qubit

CCT
012

000  000
001  001
010  010
011  011
100  100
101  101
110  111	//	The target is flipped if and only if the controls are 1
111  110

Now, all that is left is to take the values from the left column and plug them into the right column:

    CCT
    012

ACE|000  ACE|000
ACF|001  ACF|001
ADE|010  ADE|010
ADF|011  ADF|011
BCE|100  BCE|100
BCF|101  BCF|101
BDE|110  BDF|111
BDF|111  BDE|110

And finally adjust the state vector (using the binary index) to match the new order:

ADE|000›
ADF|001›
ACE|010›
ACF|011›
BCE|100›
BCF|101›
BDF|110›
BDE|111›

TOFFOLI 4 Qubit Example

Applying the column method to a 4 qubit example:

//	TOFFOLI(0, 2, 3);
//	Apply the TOFFOLI gate, one element at a time
//	C denotes the control qubit
//	T denotes the target qubit

C CT
0123

0000  0000
0001  0001
0010  0010
0011  0011
0100  0100
0101  0101
0110  0110
0111  0111
1000  1000
1001  1001
1010  1011	//	The target is flipped if and only if the controls are 1
1011  1010
1100  1100
1101  1101
1110  1111
1111  1110

Now, all that is left is to take the values from the left column and plug them into the right column:

     C CT
     0123

ACEG|0000  ACEG|0000
ACEH|0001  ACEH|0001
ACFG|0010  ACFG|0010
ACFH|0011  ACFH|0011
ADEG|0100  ADEG|0100
ADEH|0101  ADEH|0101
ADFG|0110  ADFG|0110
ADFH|0111  ADFH|0111
BCEG|1000  BCEG|1000
BCEH|1001  BCEH|1001
BCFG|1010  BCFH|1011
BCFH|1011  BCFG|1010
BDEG|1100  BDEG|1100
BDEH|1101  BDEH|1101
BDFG|1110  BDFH|1111
BDFH|1111  BDFG|1110

And finally adjust the state vector (using the binary index) to match the new order:

ACEG|0000›
ACEH|0001›
ACFG|0010›
ACFH|0011›
ADEG|0100›
ADEH|0101›
ADFG|0110›
ADFH|0111›
BCEG|1000›
BCEH|1001›
BCFH|1010›
BCFG|1011›
BDEG|1100›
BDEH|1101›
BDFH|1110›
BDFG|1111›

TOFFOLI 5 Qubit Example

Applying the column method to a 5 qubit example:

//	TOFFOLI(2, 4, 0);
//	Apply the TOFFOLI gate, one element at a time
//	C denotes the control qubit
//	T denotes the target qubit

T C C
01234

00000  00000
00001  00001
00010  00010
00011  00011
00100  00100
00101  10101	//	The target is flipped if and only if the controls are 1
00110  00110
00111  10111
01000  01000
01001  01001
01010  01010
01011  01011
01100  01100
01101  11101
01110  01110
01111  11111
10000  10000
10001  10001
10010  10010
10011  10011
10100  10100
10101  00101
10110  10110
10111  00111
11000  11000
11001  11001
11010  11010
11011  11011
11100  11100
11101  01101
11110  11110
11111  01111

Now, all that is left is to take the values from the left column and plug them into the right column:

T C C
01234

ACEGI|00000  ACEGI|00000
ACEGJ|00001  ACEGJ|00001
ACEHI|00010  ACEHI|00010
ACEHJ|00011  ACEHJ|00011
ACFGI|00100  ACFGI|00100
ACFGJ|00101  BCFGJ|10101	//	The target is flipped if and only if the controls are 1
ACFHI|00110  ACFHI|00110
ACFHJ|00111  BCFHJ|10111
ADEGI|01000  ADEGI|01000
ADEGJ|01001  ADEGJ|01001
ADEHI|01010  ADEHI|01010
ADEHJ|01011  ADEHJ|01011
ADFGI|01100  ADFGI|01100
ADFGJ|01101  BDFGJ|11101
ADFHI|01110  ADFHI|01110
ADFHJ|01111  BDFHJ|11111
BCEGI|10000  BCEGI|10000
BCEGJ|10001  BCEGJ|10001
BCEHI|10010  BCEHI|10010
BCEHJ|10011  BCEHJ|10011
BCFGI|10100  BCFGI|10100
BCFGJ|10101  ACFGJ|00101
BCFHI|10110  BCFHI|10110
BCFHJ|10111  ACFHJ|00111
BDEGI|11000  BDEGI|11000
BDEGJ|11001  BDEGJ|11001
BDEHI|11010  BDEHI|11010
BDEHJ|11011  BDEHJ|11011
BDFGI|11100  BDFGI|11100
BDFGJ|11101  ADFGJ|01101
BDFHI|11110  BDFHI|11110
BDFHJ|11111  ADFHJ|01111

And finally adjust the state vector (using the binary index) to match the new order:

ACEGI|00000›
ACEGJ|00001›
ACEHI|00010›
ACEHJ|00011›
ACFGI|00100›
BCFGJ|00101›
ACFHI|00110›
BCFHJ|00111›
ADEGI|01000›
ADEGJ|01001›
ADEHI|01010›
ADEHJ|01011›
ADFGI|01100›
BDFGJ|01101›
ADFHI|01110›
BDFHJ|01111›
BCEGI|10000›
BCEGJ|10001›
BCEHI|10010›
BCEHJ|10011›
BCFGI|10100›
ACFGJ|10101›
BCFHI|10110›
ACFHJ|10111›
BDEGI|11000›
BDEGJ|11001›
BDEHI|11010›
BDEHJ|11011›
BDFGI|11100›
ADFGJ|11101›
BDFHI|11110›
ADFHJ|11111›

The manipulation of the state vector is now complete.