Iyfjky

Question

$newcommandqr[1]$ I gave myself the task of building an operator that implements the following function: $f(0) = 0$, $f(1) = 1$, $f(2) = 1$, $f(3) = 0$. I restricted myself to $x$ up to 2 bits. That is, $f$ tells the parity of its argument.

I read that in order to be reversible, a circuit $U_f$ could be defined to have the following effect: $U_fqrx_2 qr0_1 to qrx_2qr0 oplus f(x)_1$. After doing my calculations, I think the following matrix represents $U_f$

$$beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 1 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix otimes I_2$$

However, I'm really not sure. I once read that this definition isn't complete, that I should also define the behavior for the input $qrx_2qr1$. (I'm not too clear on that.)

So --- though confused ---, I went ahead and defined $$U_fqrx_2 qr1_1 to qrx_2qr1 oplus f(x)_1.$$ Doing my calculations again, I get the following matrix

$$beginbmatrix
0 & 1 & 1 & 0\
1 & 0 & 0 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix otimes I_2$$

Now I don't know which should be my matrix.

Your matrices are wrong. For the first one, the last column is missing a non-zero entry. The top-right cell should be 1 because that's the 3->0 cell and f(3) = 0. — 8 hours ago

Dyon J Don Kiwi van Vreumingen 1826 · Answer 1 · 2018-10-18 22:08:27Z

Since your desired operation is a non-injective function, you need a third qubit and a unitary acting on all three qubits. Using an operator on your two input qubits and tensoring this with $rm I_2$ on the third qubit is not going to work as you might as well forget about the third qubit completely if that were the case.

By the way, the two matrices you present aren't unitary ($rm U^daggerrm U=rm I_4$ with $^dagger$ the conjugate transpose does not hold), and tensoring a non-unitary matrix with $rm I_2$ won't make it unitary either.

So, let's start over: take three qubits, define the first two as your input registers and the third as your output register. Then, what you want your operation to do, is this:
$$rm U_f|000rangle=|000rangle\
rm U_f|010rangle=|011rangle\
rm U_f|100rangle=|101rangle\
rm U_f|110rangle=|110rangle$$
Note that to fully define $rm U_f$, we would have to determine a desired output for the four other possible (computational basis) input states, $|!*!*1rangle$. How we do this is entirely up to us! So we can just choose something convenient, such as this:
$$rm U_f|001rangle=|001rangle\
rm U_f|011rangle=|010rangle\
rm U_f|101rangle=|100rangle\
rm U_f|111rangle=|111rangle$$
This has the following matrix form:
$$rm U_f=beginbmatrix
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&0&0&0&0\
0&0&0&0&0&1&0&0\
0&0&0&0&1&0&0&0\
0&0&0&0&0&0&1&0\
0&0&0&0&0&0&0&1
endbmatrix$$
Intuitively, this unitary is constructed with two CNOT gates, which swap the third qubit $|0rangleto|1rangle$ or $|1rangleto|0rangle$ if and only if one of the first two qubits is in a $|1rangle$ state:

enter image description here

You can check that multiplying the matrices of the two CNOTs indeed gives the same $rm U_f$.

Note this manifestly generalizes if you make x , d bits instead. You just have a CNOT for each of the d. In fact if you break this circuit, you see the parity of the first k bits for one part and the last d-k for the other. — 3 hours ago

score 2 · Answer 2 · 2018-10-18 22:39:49Z

All quantum operators must be unitary. Unitary means the conjugate-transpose of the operator is its inverse. In your case:

$UU^dagger = beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 1 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix
beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 0 & 0\
0 & 1 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix =
beginbmatrix
1 & 0 & 0 & 0\
0 & 2 & 0 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix$

So it is most certainly not unitary because $UU^dagger neq mathbbI_4$ (same as your second attempt).

There's a long way to construct functions like this, and a short way. The long way is to write out all inputs and outputs:

$U|000rangle = |000rangle$

$U|001rangle = |001rangle$

$U|010rangle = |011rangle$

$U|011rangle = |010rangle$

$U|100rangle = |101rangle$

$U|101rangle = |100rangle$

$U|110rangle = |110rangle$

$U|111rangle = |111rangle$

You can then pretty easily construct the operator from this.

An easier way is to use projection operators & matrix addition to implement "if-then" semantics with matrices:

$|0ranglelangle0| = beginbmatrix 1 \ 0 endbmatrix beginbmatrix 1 & 0 endbmatrix = beginbmatrix 1 & 0 \ 0 & 0 endbmatrix$

which is called a projection operator. Use projection operators to only apply an operation on specific states - here, $|0rangle$.

A huge benefit of this projectors & addition approach is that you never have to actually write out the full matrix, which can become enormous as the number of qbits increase - 3-qbit 8x8 matrices already have 64 elements! This is your first step into using symbolic rather than matrix reasoning. For example, we can use the rules of linear algebra to calculate the action of our $U$ on some input:

Now, matrix multiplication distributes over addition. This means we have:

Now, note we have the following four terms:

$langle00|10rangle, langle01|10rangle, langle10|10rangle, langle11|10rangle$

These are called inner products, or dot products and here all of them are zero except for $langle10|10rangle$ - the dot product of $|10rangle$ with itself:

$langle10|10rangle = beginbmatrix 0 & 0 & 1 & 0endbmatrix
beginbmatrix0 \ 0 \ 1 \ 0endbmatrix = 1$

Since the other terms are all zero, they all cancel out:

$requirecancel cancel + cancel1rangle + |10ranglecdot 1 otimes X_2 |1rangle + cancel1rangle$

So we are left with:

$|10rangle otimes X_2 |1rangle$

Where of course $X_2|1rangle = |0rangle$, so:

$|10rangle otimes |0rangle = |100rangle$

And we calculated $U|101rangle = |100rangle$ as expected, without once having to write out a huge inconvenient matrix!

cnada 96818 · Answer 3 · 2018-10-19 01:41:55Z

Your bit strings x in the case when you specify 2 bits are 00, 01, 10, 11.
Now you want to output the result in another bit/qubit.

Whether the outpit bit/qubit is initialized as 0 or 1 should not change your unitary operation. The only thing changing is the initial quantum state your system is onto where you apply the unitary operation representing your function.

In this case, the implementation is straightforward. This is a first CNOT with first qubit of register x as control and the output qubit as target followed by another CNOT with the second qubit of x as control. If you input x=00, nothing happens. If x=01 or 10, you apply one CNOT which adds 1 to the target (definition of CNOT). If x=11, the two CNOTs are applied so you add 1 to the target twice and 1 + 1 = 0 when having one output bit.

To get the unitary, you can just take the unitary matrix of the CNOT, tensor product with the identity matrix (but respect the order when you write). You do this for the first CNOT giving you one unitary $U_1$, then the second giving $ U_2 $ and finally multiply $ U_2 * U_1 $ to get your unitary operator.

Dyon J Don Kiwi van Vreumingen 1826 · Answer 4 · 2018-10-18 22:08:27Z

Since your desired operation is a non-injective function, you need a third qubit and a unitary acting on all three qubits. Using an operator on your two input qubits and tensoring this with $rm I_2$ on the third qubit is not going to work as you might as well forget about the third qubit completely if that were the case.

By the way, the two matrices you present aren't unitary ($rm U^daggerrm U=rm I_4$ with $^dagger$ the conjugate transpose does not hold), and tensoring a non-unitary matrix with $rm I_2$ won't make it unitary either.

So, let's start over: take three qubits, define the first two as your input registers and the third as your output register. Then, what you want your operation to do, is this:
$$rm U_f|000rangle=|000rangle\
rm U_f|010rangle=|011rangle\
rm U_f|100rangle=|101rangle\
rm U_f|110rangle=|110rangle$$
Note that to fully define $rm U_f$, we would have to determine a desired output for the four other possible (computational basis) input states, $|!*!*1rangle$. How we do this is entirely up to us! So we can just choose something convenient, such as this:
$$rm U_f|001rangle=|001rangle\
rm U_f|011rangle=|010rangle\
rm U_f|101rangle=|100rangle\
rm U_f|111rangle=|111rangle$$
This has the following matrix form:
$$rm U_f=beginbmatrix
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&0&0&0&0\
0&0&0&0&0&1&0&0\
0&0&0&0&1&0&0&0\
0&0&0&0&0&0&1&0\
0&0&0&0&0&0&0&1
endbmatrix$$
Intuitively, this unitary is constructed with two CNOT gates, which swap the third qubit $|0rangleto|1rangle$ or $|1rangleto|0rangle$ if and only if one of the first two qubits is in a $|1rangle$ state:

enter image description here

You can check that multiplying the matrices of the two CNOTs indeed gives the same $rm U_f$.

Note this manifestly generalizes if you make x , d bits instead. You just have a CNOT for each of the d. In fact if you break this circuit, you see the parity of the first k bits for one part and the last d-k for the other. — 3 hours ago

score 2 · Answer 5 · 2018-10-18 22:39:49Z

All quantum operators must be unitary. Unitary means the conjugate-transpose of the operator is its inverse. In your case:

$UU^dagger = beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 1 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix
beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 0 & 0\
0 & 1 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix =
beginbmatrix
1 & 0 & 0 & 0\
0 & 2 & 0 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix$

So it is most certainly not unitary because $UU^dagger neq mathbbI_4$ (same as your second attempt).

There's a long way to construct functions like this, and a short way. The long way is to write out all inputs and outputs:

$U|000rangle = |000rangle$

$U|001rangle = |001rangle$

$U|010rangle = |011rangle$

$U|011rangle = |010rangle$

$U|100rangle = |101rangle$

$U|101rangle = |100rangle$

$U|110rangle = |110rangle$

$U|111rangle = |111rangle$

You can then pretty easily construct the operator from this.

An easier way is to use projection operators & matrix addition to implement "if-then" semantics with matrices:

$|0ranglelangle0| = beginbmatrix 1 \ 0 endbmatrix beginbmatrix 1 & 0 endbmatrix = beginbmatrix 1 & 0 \ 0 & 0 endbmatrix$

which is called a projection operator. Use projection operators to only apply an operation on specific states - here, $|0rangle$.

A huge benefit of this projectors & addition approach is that you never have to actually write out the full matrix, which can become enormous as the number of qbits increase - 3-qbit 8x8 matrices already have 64 elements! This is your first step into using symbolic rather than matrix reasoning. For example, we can use the rules of linear algebra to calculate the action of our $U$ on some input:

Now, matrix multiplication distributes over addition. This means we have:

Now, note we have the following four terms:

$langle00|10rangle, langle01|10rangle, langle10|10rangle, langle11|10rangle$

These are called inner products, or dot products and here all of them are zero except for $langle10|10rangle$ - the dot product of $|10rangle$ with itself:

$langle10|10rangle = beginbmatrix 0 & 0 & 1 & 0endbmatrix
beginbmatrix0 \ 0 \ 1 \ 0endbmatrix = 1$

Since the other terms are all zero, they all cancel out:

$requirecancel cancel + cancel1rangle + |10ranglecdot 1 otimes X_2 |1rangle + cancel1rangle$

So we are left with:

$|10rangle otimes X_2 |1rangle$

Where of course $X_2|1rangle = |0rangle$, so:

$|10rangle otimes |0rangle = |100rangle$

And we calculated $U|101rangle = |100rangle$ as expected, without once having to write out a huge inconvenient matrix!

cnada 96818 · Answer 6 · 2018-10-19 01:41:55Z

Your bit strings x in the case when you specify 2 bits are 00, 01, 10, 11.
Now you want to output the result in another bit/qubit.

Whether the outpit bit/qubit is initialized as 0 or 1 should not change your unitary operation. The only thing changing is the initial quantum state your system is onto where you apply the unitary operation representing your function.

In this case, the implementation is straightforward. This is a first CNOT with first qubit of register x as control and the output qubit as target followed by another CNOT with the second qubit of x as control. If you input x=00, nothing happens. If x=01 or 10, you apply one CNOT which adds 1 to the target (definition of CNOT). If x=11, the two CNOTs are applied so you add 1 to the target twice and 1 + 1 = 0 when having one output bit.

To get the unitary, you can just take the unitary matrix of the CNOT, tensor product with the identity matrix (but respect the order when you write). You do this for the first CNOT giving you one unitary $U_1$, then the second giving $ U_2 $ and finally multiply $ U_2 * U_1 $ to get your unitary operator.

Search This Blog

Iyfjky

What is the matrix for the operator that implements a function to tell the parity of its argument?

3 Answers
3

Your Answer

Post as a guest

3 Answers
3

3 Answers
3

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

Category

Random preview

What is the matrix for the operator that implements a function to tell the parity of its argument?

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

3 Answers
3

3 Answers
3

3 Answers
3

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor