Composing the CNOT gate as a tensor product of two level matrices












4












$begingroup$


I don't understand, why is the control not gate used so often. As far as I understand it, if you apply two 2 level operations on two qubits then you get a 4 x 4 matrix by the tensor product. So how would you express the CNOT gate as a product of the one matrix acting upon the first qubit and the second acting on the second qubit?



Another thing which I have difficulty understanding is why we use so many single qubits and CNOT gates for implementing the Toffoli gate? Can't we implement it using just an AND between the first two qubits and then applying a controlled NOT for the third one?










share|improve this question











$endgroup$












  • $begingroup$
    Refer to this question: How to construct matrix of regular and “flipped” 2-qubit CNOT?
    $endgroup$
    – Josu Etxezarreta Martinez
    Feb 7 at 14:17


















4












$begingroup$


I don't understand, why is the control not gate used so often. As far as I understand it, if you apply two 2 level operations on two qubits then you get a 4 x 4 matrix by the tensor product. So how would you express the CNOT gate as a product of the one matrix acting upon the first qubit and the second acting on the second qubit?



Another thing which I have difficulty understanding is why we use so many single qubits and CNOT gates for implementing the Toffoli gate? Can't we implement it using just an AND between the first two qubits and then applying a controlled NOT for the third one?










share|improve this question











$endgroup$












  • $begingroup$
    Refer to this question: How to construct matrix of regular and “flipped” 2-qubit CNOT?
    $endgroup$
    – Josu Etxezarreta Martinez
    Feb 7 at 14:17
















4












4








4





$begingroup$


I don't understand, why is the control not gate used so often. As far as I understand it, if you apply two 2 level operations on two qubits then you get a 4 x 4 matrix by the tensor product. So how would you express the CNOT gate as a product of the one matrix acting upon the first qubit and the second acting on the second qubit?



Another thing which I have difficulty understanding is why we use so many single qubits and CNOT gates for implementing the Toffoli gate? Can't we implement it using just an AND between the first two qubits and then applying a controlled NOT for the third one?










share|improve this question











$endgroup$




I don't understand, why is the control not gate used so often. As far as I understand it, if you apply two 2 level operations on two qubits then you get a 4 x 4 matrix by the tensor product. So how would you express the CNOT gate as a product of the one matrix acting upon the first qubit and the second acting on the second qubit?



Another thing which I have difficulty understanding is why we use so many single qubits and CNOT gates for implementing the Toffoli gate? Can't we implement it using just an AND between the first two qubits and then applying a controlled NOT for the third one?







quantum-gate gate-synthesis tensor-product






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Feb 8 at 11:32









glS

4,333740




4,333740










asked Feb 7 at 13:49









bilanushbilanush

37016




37016












  • $begingroup$
    Refer to this question: How to construct matrix of regular and “flipped” 2-qubit CNOT?
    $endgroup$
    – Josu Etxezarreta Martinez
    Feb 7 at 14:17




















  • $begingroup$
    Refer to this question: How to construct matrix of regular and “flipped” 2-qubit CNOT?
    $endgroup$
    – Josu Etxezarreta Martinez
    Feb 7 at 14:17


















$begingroup$
Refer to this question: How to construct matrix of regular and “flipped” 2-qubit CNOT?
$endgroup$
– Josu Etxezarreta Martinez
Feb 7 at 14:17






$begingroup$
Refer to this question: How to construct matrix of regular and “flipped” 2-qubit CNOT?
$endgroup$
– Josu Etxezarreta Martinez
Feb 7 at 14:17












2 Answers
2






active

oldest

votes


















6












$begingroup$

The whole point is that CNOT cannot be written in the form $Aotimes B$. This is absolutely essential because if we only ever had operators of the form $Aotimes B$, states of the form $|psirangleotimes|phirangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer.



As for the Toffoli construction you describe, we require that in a quantum circuit, all gates are reversible. The AND gate is not reversible as you can see from the way the number of outputs is smaller than the number of inputs (so it's impossible to know what the inputs were just by looking at the outputs).





The above answers the question actually asked. However, I infer from the follow up comments of the OP, both here and on other questions, that there's something else that they're trying to get at. Here's my attempt to resolve some confusion.




Any $Ntimes N$ matrix can be composed as a product of "two-level matrices".




This is the normal matrix product, not the tensor product. A "two-level matrix" in this context is a matrix which is the identity everywhere except for two basis elements $s$ and $t$, on which the $2times 2$ matrix is an arbitrary unitary matrix. The controlled-not is by no means an exception to this rule. In fact, it's a particularly simple example because controlled-not is a two-level matrix where $s=10$ and $t=11$. That makes it a particularly natural building block which allows the further statement




Any $2^ntimes 2^n$ two-level matrix can be decomposed in terms of $2times 2$ two-level matrices and the special case $4times 4$ two-level matrix that is controlled-not.




remembering that any system on which the gate does not act requires us to take the tensor product of the operator with identity in order to make it act on the correct dimension.






share|improve this answer











$endgroup$













  • $begingroup$
    As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
    $endgroup$
    – bilanush
    Feb 7 at 17:15












  • $begingroup$
    As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
    $endgroup$
    – bilanush
    Feb 7 at 17:31










  • $begingroup$
    Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
    $endgroup$
    – bilanush
    Feb 7 at 18:35






  • 1




    $begingroup$
    "can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
    $endgroup$
    – DaftWullie
    Feb 7 at 20:46






  • 1




    $begingroup$
    @bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
    $endgroup$
    – DaftWullie
    Feb 20 at 12:08



















4












$begingroup$

Any two qubit Controlled-U gate is not decomposable as $Aotimes B$ in general. The whole point is that a conditional operator has a non-local nature and it gives rise to non-trivial correlations when operated on a state.



The Physics behind is that; imagine a Controlled operation which can be factored as $Aotimes B$, and the sub-systems (or the two qubits) are separated non-locally in space. then the only way to perform a controlled conditional operation is to measure the state of a first qubit, convey the outcome classically to the second qubit and apply the desired unitary on the second qubit, and finally re-initialize the first qubit. But now note that this is NOT actually a 'true' controlled gate because it cannot work for an arbitrary control qubit.



Hence, the actual nature of a conditional gate is non-local, which essentially implies that it cannot be factored as $Aotimes B$ over the sub-spaces. The intuition can be taken as the operation reads system $A$ and simultaneously changes system $B$ based on the state of system $A$. This is strictly non-local in nature. Physically how it is implemented in experiments is most often by a single exchange of quanta between the states, which is triggered by the state of one sub-system. Hence, this gives rise to entanglement between the sub-systems. It is most often called the 'entanglement generator'.



Also, you can think of $operatorname{CNOT}$ gate to be the most simplified two-qubit gate which can generate the class of two-qubit non-local gates when combined with few other gates. This is already proved by the Universality of single-qubit gates and the $operatorname{CNOT}$ gate.



About the Toffoli gate, the most obvious way to implement it (after taking in mind the universality) is to decompose it in parts of $operatorname{CNOT}$ gates and single qubit gates. This is what is done. And because reversibility is a must requirement for a quantum operation, you cannot use any analogous irreversible gate like the $operatorname{AND}$ gate in quantum circuits. To perform the $operatorname{AND}$ analogous operation as you pointed out, this is further broken up in parts of the single qubit and $operatorname{CNOT}$ gates (to ensure the reversibility and unitarity).



PS: One essential reason why this decomposition is done because in experiments all we can implement are these single qubit and $operatorname{CNOT}$ gates only. Any such protocol must be decomposed in these gates to cope up with some experimental implementation. And these are intuitive as well, rather than using multi-qubit gates which are nothing but a series of the single qubit gates and $operatorname{CNOT}$s.






share|improve this answer











$endgroup$













  • $begingroup$
    Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
    $endgroup$
    – bilanush
    Feb 7 at 20:12










  • $begingroup$
    And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
    $endgroup$
    – bilanush
    Feb 7 at 20:14










  • $begingroup$
    By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
    $endgroup$
    – Siddhānt Singh
    Feb 7 at 20:16






  • 1




    $begingroup$
    Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
    $endgroup$
    – DaftWullie
    Feb 8 at 16:22






  • 1




    $begingroup$
    It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
    $endgroup$
    – DaftWullie
    Feb 20 at 20:14












Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "694"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5409%2fcomposing-the-cnot-gate-as-a-tensor-product-of-two-level-matrices%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









6












$begingroup$

The whole point is that CNOT cannot be written in the form $Aotimes B$. This is absolutely essential because if we only ever had operators of the form $Aotimes B$, states of the form $|psirangleotimes|phirangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer.



As for the Toffoli construction you describe, we require that in a quantum circuit, all gates are reversible. The AND gate is not reversible as you can see from the way the number of outputs is smaller than the number of inputs (so it's impossible to know what the inputs were just by looking at the outputs).





The above answers the question actually asked. However, I infer from the follow up comments of the OP, both here and on other questions, that there's something else that they're trying to get at. Here's my attempt to resolve some confusion.




Any $Ntimes N$ matrix can be composed as a product of "two-level matrices".




This is the normal matrix product, not the tensor product. A "two-level matrix" in this context is a matrix which is the identity everywhere except for two basis elements $s$ and $t$, on which the $2times 2$ matrix is an arbitrary unitary matrix. The controlled-not is by no means an exception to this rule. In fact, it's a particularly simple example because controlled-not is a two-level matrix where $s=10$ and $t=11$. That makes it a particularly natural building block which allows the further statement




Any $2^ntimes 2^n$ two-level matrix can be decomposed in terms of $2times 2$ two-level matrices and the special case $4times 4$ two-level matrix that is controlled-not.




remembering that any system on which the gate does not act requires us to take the tensor product of the operator with identity in order to make it act on the correct dimension.






share|improve this answer











$endgroup$













  • $begingroup$
    As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
    $endgroup$
    – bilanush
    Feb 7 at 17:15












  • $begingroup$
    As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
    $endgroup$
    – bilanush
    Feb 7 at 17:31










  • $begingroup$
    Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
    $endgroup$
    – bilanush
    Feb 7 at 18:35






  • 1




    $begingroup$
    "can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
    $endgroup$
    – DaftWullie
    Feb 7 at 20:46






  • 1




    $begingroup$
    @bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
    $endgroup$
    – DaftWullie
    Feb 20 at 12:08
















6












$begingroup$

The whole point is that CNOT cannot be written in the form $Aotimes B$. This is absolutely essential because if we only ever had operators of the form $Aotimes B$, states of the form $|psirangleotimes|phirangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer.



As for the Toffoli construction you describe, we require that in a quantum circuit, all gates are reversible. The AND gate is not reversible as you can see from the way the number of outputs is smaller than the number of inputs (so it's impossible to know what the inputs were just by looking at the outputs).





The above answers the question actually asked. However, I infer from the follow up comments of the OP, both here and on other questions, that there's something else that they're trying to get at. Here's my attempt to resolve some confusion.




Any $Ntimes N$ matrix can be composed as a product of "two-level matrices".




This is the normal matrix product, not the tensor product. A "two-level matrix" in this context is a matrix which is the identity everywhere except for two basis elements $s$ and $t$, on which the $2times 2$ matrix is an arbitrary unitary matrix. The controlled-not is by no means an exception to this rule. In fact, it's a particularly simple example because controlled-not is a two-level matrix where $s=10$ and $t=11$. That makes it a particularly natural building block which allows the further statement




Any $2^ntimes 2^n$ two-level matrix can be decomposed in terms of $2times 2$ two-level matrices and the special case $4times 4$ two-level matrix that is controlled-not.




remembering that any system on which the gate does not act requires us to take the tensor product of the operator with identity in order to make it act on the correct dimension.






share|improve this answer











$endgroup$













  • $begingroup$
    As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
    $endgroup$
    – bilanush
    Feb 7 at 17:15












  • $begingroup$
    As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
    $endgroup$
    – bilanush
    Feb 7 at 17:31










  • $begingroup$
    Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
    $endgroup$
    – bilanush
    Feb 7 at 18:35






  • 1




    $begingroup$
    "can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
    $endgroup$
    – DaftWullie
    Feb 7 at 20:46






  • 1




    $begingroup$
    @bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
    $endgroup$
    – DaftWullie
    Feb 20 at 12:08














6












6








6





$begingroup$

The whole point is that CNOT cannot be written in the form $Aotimes B$. This is absolutely essential because if we only ever had operators of the form $Aotimes B$, states of the form $|psirangleotimes|phirangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer.



As for the Toffoli construction you describe, we require that in a quantum circuit, all gates are reversible. The AND gate is not reversible as you can see from the way the number of outputs is smaller than the number of inputs (so it's impossible to know what the inputs were just by looking at the outputs).





The above answers the question actually asked. However, I infer from the follow up comments of the OP, both here and on other questions, that there's something else that they're trying to get at. Here's my attempt to resolve some confusion.




Any $Ntimes N$ matrix can be composed as a product of "two-level matrices".




This is the normal matrix product, not the tensor product. A "two-level matrix" in this context is a matrix which is the identity everywhere except for two basis elements $s$ and $t$, on which the $2times 2$ matrix is an arbitrary unitary matrix. The controlled-not is by no means an exception to this rule. In fact, it's a particularly simple example because controlled-not is a two-level matrix where $s=10$ and $t=11$. That makes it a particularly natural building block which allows the further statement




Any $2^ntimes 2^n$ two-level matrix can be decomposed in terms of $2times 2$ two-level matrices and the special case $4times 4$ two-level matrix that is controlled-not.




remembering that any system on which the gate does not act requires us to take the tensor product of the operator with identity in order to make it act on the correct dimension.






share|improve this answer











$endgroup$



The whole point is that CNOT cannot be written in the form $Aotimes B$. This is absolutely essential because if we only ever had operators of the form $Aotimes B$, states of the form $|psirangleotimes|phirangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer.



As for the Toffoli construction you describe, we require that in a quantum circuit, all gates are reversible. The AND gate is not reversible as you can see from the way the number of outputs is smaller than the number of inputs (so it's impossible to know what the inputs were just by looking at the outputs).





The above answers the question actually asked. However, I infer from the follow up comments of the OP, both here and on other questions, that there's something else that they're trying to get at. Here's my attempt to resolve some confusion.




Any $Ntimes N$ matrix can be composed as a product of "two-level matrices".




This is the normal matrix product, not the tensor product. A "two-level matrix" in this context is a matrix which is the identity everywhere except for two basis elements $s$ and $t$, on which the $2times 2$ matrix is an arbitrary unitary matrix. The controlled-not is by no means an exception to this rule. In fact, it's a particularly simple example because controlled-not is a two-level matrix where $s=10$ and $t=11$. That makes it a particularly natural building block which allows the further statement




Any $2^ntimes 2^n$ two-level matrix can be decomposed in terms of $2times 2$ two-level matrices and the special case $4times 4$ two-level matrix that is controlled-not.




remembering that any system on which the gate does not act requires us to take the tensor product of the operator with identity in order to make it act on the correct dimension.







share|improve this answer














share|improve this answer



share|improve this answer








edited Feb 20 at 12:06

























answered Feb 7 at 14:16









DaftWullieDaftWullie

15.2k1542




15.2k1542












  • $begingroup$
    As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
    $endgroup$
    – bilanush
    Feb 7 at 17:15












  • $begingroup$
    As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
    $endgroup$
    – bilanush
    Feb 7 at 17:31










  • $begingroup$
    Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
    $endgroup$
    – bilanush
    Feb 7 at 18:35






  • 1




    $begingroup$
    "can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
    $endgroup$
    – DaftWullie
    Feb 7 at 20:46






  • 1




    $begingroup$
    @bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
    $endgroup$
    – DaftWullie
    Feb 20 at 12:08


















  • $begingroup$
    As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
    $endgroup$
    – bilanush
    Feb 7 at 17:15












  • $begingroup$
    As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
    $endgroup$
    – bilanush
    Feb 7 at 17:31










  • $begingroup$
    Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
    $endgroup$
    – bilanush
    Feb 7 at 18:35






  • 1




    $begingroup$
    "can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
    $endgroup$
    – DaftWullie
    Feb 7 at 20:46






  • 1




    $begingroup$
    @bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
    $endgroup$
    – DaftWullie
    Feb 20 at 12:08
















$begingroup$
As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
$endgroup$
– bilanush
Feb 7 at 17:15






$begingroup$
As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate
$endgroup$
– bilanush
Feb 7 at 17:15














$begingroup$
As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
$endgroup$
– bilanush
Feb 7 at 17:31




$begingroup$
As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No?
$endgroup$
– bilanush
Feb 7 at 17:31












$begingroup$
Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
$endgroup$
– bilanush
Feb 7 at 18:35




$begingroup$
Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation.
$endgroup$
– bilanush
Feb 7 at 18:35




1




1




$begingroup$
"can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
$endgroup$
– DaftWullie
Feb 7 at 20:46




$begingroup$
"can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles.
$endgroup$
– DaftWullie
Feb 7 at 20:46




1




1




$begingroup$
@bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
$endgroup$
– DaftWullie
Feb 20 at 12:08




$begingroup$
@bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other.
$endgroup$
– DaftWullie
Feb 20 at 12:08













4












$begingroup$

Any two qubit Controlled-U gate is not decomposable as $Aotimes B$ in general. The whole point is that a conditional operator has a non-local nature and it gives rise to non-trivial correlations when operated on a state.



The Physics behind is that; imagine a Controlled operation which can be factored as $Aotimes B$, and the sub-systems (or the two qubits) are separated non-locally in space. then the only way to perform a controlled conditional operation is to measure the state of a first qubit, convey the outcome classically to the second qubit and apply the desired unitary on the second qubit, and finally re-initialize the first qubit. But now note that this is NOT actually a 'true' controlled gate because it cannot work for an arbitrary control qubit.



Hence, the actual nature of a conditional gate is non-local, which essentially implies that it cannot be factored as $Aotimes B$ over the sub-spaces. The intuition can be taken as the operation reads system $A$ and simultaneously changes system $B$ based on the state of system $A$. This is strictly non-local in nature. Physically how it is implemented in experiments is most often by a single exchange of quanta between the states, which is triggered by the state of one sub-system. Hence, this gives rise to entanglement between the sub-systems. It is most often called the 'entanglement generator'.



Also, you can think of $operatorname{CNOT}$ gate to be the most simplified two-qubit gate which can generate the class of two-qubit non-local gates when combined with few other gates. This is already proved by the Universality of single-qubit gates and the $operatorname{CNOT}$ gate.



About the Toffoli gate, the most obvious way to implement it (after taking in mind the universality) is to decompose it in parts of $operatorname{CNOT}$ gates and single qubit gates. This is what is done. And because reversibility is a must requirement for a quantum operation, you cannot use any analogous irreversible gate like the $operatorname{AND}$ gate in quantum circuits. To perform the $operatorname{AND}$ analogous operation as you pointed out, this is further broken up in parts of the single qubit and $operatorname{CNOT}$ gates (to ensure the reversibility and unitarity).



PS: One essential reason why this decomposition is done because in experiments all we can implement are these single qubit and $operatorname{CNOT}$ gates only. Any such protocol must be decomposed in these gates to cope up with some experimental implementation. And these are intuitive as well, rather than using multi-qubit gates which are nothing but a series of the single qubit gates and $operatorname{CNOT}$s.






share|improve this answer











$endgroup$













  • $begingroup$
    Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
    $endgroup$
    – bilanush
    Feb 7 at 20:12










  • $begingroup$
    And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
    $endgroup$
    – bilanush
    Feb 7 at 20:14










  • $begingroup$
    By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
    $endgroup$
    – Siddhānt Singh
    Feb 7 at 20:16






  • 1




    $begingroup$
    Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
    $endgroup$
    – DaftWullie
    Feb 8 at 16:22






  • 1




    $begingroup$
    It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
    $endgroup$
    – DaftWullie
    Feb 20 at 20:14
















4












$begingroup$

Any two qubit Controlled-U gate is not decomposable as $Aotimes B$ in general. The whole point is that a conditional operator has a non-local nature and it gives rise to non-trivial correlations when operated on a state.



The Physics behind is that; imagine a Controlled operation which can be factored as $Aotimes B$, and the sub-systems (or the two qubits) are separated non-locally in space. then the only way to perform a controlled conditional operation is to measure the state of a first qubit, convey the outcome classically to the second qubit and apply the desired unitary on the second qubit, and finally re-initialize the first qubit. But now note that this is NOT actually a 'true' controlled gate because it cannot work for an arbitrary control qubit.



Hence, the actual nature of a conditional gate is non-local, which essentially implies that it cannot be factored as $Aotimes B$ over the sub-spaces. The intuition can be taken as the operation reads system $A$ and simultaneously changes system $B$ based on the state of system $A$. This is strictly non-local in nature. Physically how it is implemented in experiments is most often by a single exchange of quanta between the states, which is triggered by the state of one sub-system. Hence, this gives rise to entanglement between the sub-systems. It is most often called the 'entanglement generator'.



Also, you can think of $operatorname{CNOT}$ gate to be the most simplified two-qubit gate which can generate the class of two-qubit non-local gates when combined with few other gates. This is already proved by the Universality of single-qubit gates and the $operatorname{CNOT}$ gate.



About the Toffoli gate, the most obvious way to implement it (after taking in mind the universality) is to decompose it in parts of $operatorname{CNOT}$ gates and single qubit gates. This is what is done. And because reversibility is a must requirement for a quantum operation, you cannot use any analogous irreversible gate like the $operatorname{AND}$ gate in quantum circuits. To perform the $operatorname{AND}$ analogous operation as you pointed out, this is further broken up in parts of the single qubit and $operatorname{CNOT}$ gates (to ensure the reversibility and unitarity).



PS: One essential reason why this decomposition is done because in experiments all we can implement are these single qubit and $operatorname{CNOT}$ gates only. Any such protocol must be decomposed in these gates to cope up with some experimental implementation. And these are intuitive as well, rather than using multi-qubit gates which are nothing but a series of the single qubit gates and $operatorname{CNOT}$s.






share|improve this answer











$endgroup$













  • $begingroup$
    Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
    $endgroup$
    – bilanush
    Feb 7 at 20:12










  • $begingroup$
    And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
    $endgroup$
    – bilanush
    Feb 7 at 20:14










  • $begingroup$
    By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
    $endgroup$
    – Siddhānt Singh
    Feb 7 at 20:16






  • 1




    $begingroup$
    Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
    $endgroup$
    – DaftWullie
    Feb 8 at 16:22






  • 1




    $begingroup$
    It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
    $endgroup$
    – DaftWullie
    Feb 20 at 20:14














4












4








4





$begingroup$

Any two qubit Controlled-U gate is not decomposable as $Aotimes B$ in general. The whole point is that a conditional operator has a non-local nature and it gives rise to non-trivial correlations when operated on a state.



The Physics behind is that; imagine a Controlled operation which can be factored as $Aotimes B$, and the sub-systems (or the two qubits) are separated non-locally in space. then the only way to perform a controlled conditional operation is to measure the state of a first qubit, convey the outcome classically to the second qubit and apply the desired unitary on the second qubit, and finally re-initialize the first qubit. But now note that this is NOT actually a 'true' controlled gate because it cannot work for an arbitrary control qubit.



Hence, the actual nature of a conditional gate is non-local, which essentially implies that it cannot be factored as $Aotimes B$ over the sub-spaces. The intuition can be taken as the operation reads system $A$ and simultaneously changes system $B$ based on the state of system $A$. This is strictly non-local in nature. Physically how it is implemented in experiments is most often by a single exchange of quanta between the states, which is triggered by the state of one sub-system. Hence, this gives rise to entanglement between the sub-systems. It is most often called the 'entanglement generator'.



Also, you can think of $operatorname{CNOT}$ gate to be the most simplified two-qubit gate which can generate the class of two-qubit non-local gates when combined with few other gates. This is already proved by the Universality of single-qubit gates and the $operatorname{CNOT}$ gate.



About the Toffoli gate, the most obvious way to implement it (after taking in mind the universality) is to decompose it in parts of $operatorname{CNOT}$ gates and single qubit gates. This is what is done. And because reversibility is a must requirement for a quantum operation, you cannot use any analogous irreversible gate like the $operatorname{AND}$ gate in quantum circuits. To perform the $operatorname{AND}$ analogous operation as you pointed out, this is further broken up in parts of the single qubit and $operatorname{CNOT}$ gates (to ensure the reversibility and unitarity).



PS: One essential reason why this decomposition is done because in experiments all we can implement are these single qubit and $operatorname{CNOT}$ gates only. Any such protocol must be decomposed in these gates to cope up with some experimental implementation. And these are intuitive as well, rather than using multi-qubit gates which are nothing but a series of the single qubit gates and $operatorname{CNOT}$s.






share|improve this answer











$endgroup$



Any two qubit Controlled-U gate is not decomposable as $Aotimes B$ in general. The whole point is that a conditional operator has a non-local nature and it gives rise to non-trivial correlations when operated on a state.



The Physics behind is that; imagine a Controlled operation which can be factored as $Aotimes B$, and the sub-systems (or the two qubits) are separated non-locally in space. then the only way to perform a controlled conditional operation is to measure the state of a first qubit, convey the outcome classically to the second qubit and apply the desired unitary on the second qubit, and finally re-initialize the first qubit. But now note that this is NOT actually a 'true' controlled gate because it cannot work for an arbitrary control qubit.



Hence, the actual nature of a conditional gate is non-local, which essentially implies that it cannot be factored as $Aotimes B$ over the sub-spaces. The intuition can be taken as the operation reads system $A$ and simultaneously changes system $B$ based on the state of system $A$. This is strictly non-local in nature. Physically how it is implemented in experiments is most often by a single exchange of quanta between the states, which is triggered by the state of one sub-system. Hence, this gives rise to entanglement between the sub-systems. It is most often called the 'entanglement generator'.



Also, you can think of $operatorname{CNOT}$ gate to be the most simplified two-qubit gate which can generate the class of two-qubit non-local gates when combined with few other gates. This is already proved by the Universality of single-qubit gates and the $operatorname{CNOT}$ gate.



About the Toffoli gate, the most obvious way to implement it (after taking in mind the universality) is to decompose it in parts of $operatorname{CNOT}$ gates and single qubit gates. This is what is done. And because reversibility is a must requirement for a quantum operation, you cannot use any analogous irreversible gate like the $operatorname{AND}$ gate in quantum circuits. To perform the $operatorname{AND}$ analogous operation as you pointed out, this is further broken up in parts of the single qubit and $operatorname{CNOT}$ gates (to ensure the reversibility and unitarity).



PS: One essential reason why this decomposition is done because in experiments all we can implement are these single qubit and $operatorname{CNOT}$ gates only. Any such protocol must be decomposed in these gates to cope up with some experimental implementation. And these are intuitive as well, rather than using multi-qubit gates which are nothing but a series of the single qubit gates and $operatorname{CNOT}$s.







share|improve this answer














share|improve this answer



share|improve this answer








edited Feb 8 at 0:42

























answered Feb 7 at 20:02









Siddhānt SinghSiddhānt Singh

1




1












  • $begingroup$
    Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
    $endgroup$
    – bilanush
    Feb 7 at 20:12










  • $begingroup$
    And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
    $endgroup$
    – bilanush
    Feb 7 at 20:14










  • $begingroup$
    By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
    $endgroup$
    – Siddhānt Singh
    Feb 7 at 20:16






  • 1




    $begingroup$
    Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
    $endgroup$
    – DaftWullie
    Feb 8 at 16:22






  • 1




    $begingroup$
    It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
    $endgroup$
    – DaftWullie
    Feb 20 at 20:14


















  • $begingroup$
    Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
    $endgroup$
    – bilanush
    Feb 7 at 20:12










  • $begingroup$
    And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
    $endgroup$
    – bilanush
    Feb 7 at 20:14










  • $begingroup$
    By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
    $endgroup$
    – Siddhānt Singh
    Feb 7 at 20:16






  • 1




    $begingroup$
    Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
    $endgroup$
    – DaftWullie
    Feb 8 at 16:22






  • 1




    $begingroup$
    It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
    $endgroup$
    – DaftWullie
    Feb 20 at 20:14
















$begingroup$
Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
$endgroup$
– bilanush
Feb 7 at 20:12




$begingroup$
Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation?
$endgroup$
– bilanush
Feb 7 at 20:12












$begingroup$
And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
$endgroup$
– bilanush
Feb 7 at 20:14




$begingroup$
And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception?
$endgroup$
– bilanush
Feb 7 at 20:14












$begingroup$
By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
$endgroup$
– Siddhānt Singh
Feb 7 at 20:16




$begingroup$
By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local.
$endgroup$
– Siddhānt Singh
Feb 7 at 20:16




1




1




$begingroup$
Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
$endgroup$
– DaftWullie
Feb 8 at 16:22




$begingroup$
Beware the swap gate! It cannot be written in the form $Aotimes B$, but it is also not entangling.
$endgroup$
– DaftWullie
Feb 8 at 16:22




1




1




$begingroup$
It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
$endgroup$
– DaftWullie
Feb 20 at 20:14




$begingroup$
It’s still the same issue. Nobody claims every gate can be written in the form $Aotimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form.
$endgroup$
– DaftWullie
Feb 20 at 20:14


















draft saved

draft discarded




















































Thanks for contributing an answer to Quantum Computing Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5409%2fcomposing-the-cnot-gate-as-a-tensor-product-of-two-level-matrices%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅