Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading some papers on the efficient simulation of quantum circuits where the gates are restricted to Clifford circuits (Hadamard, PHASE and CNOT gates) and was curious about the following question:

Given an initial state $|\psi\rangle$ $$ |\psi\rangle = \left[ \begin{array}{c} \cos(\psi_0) \\ \sin(\psi_0) \end{array} \right] \otimes \left[ \begin{array}{c} \cos(\psi_1) \\ \sin(\psi_1) \end{array} \right] \otimes \left[ \begin{array}{c} \cos(\psi_2) \\ \sin(\psi_2) \end{array} \right] $$ and a 2x2 rotation matrix $R_\theta$ $$ R_\theta = \left[ \begin{array}{cc} \cos(\theta) & \sin(\theta) \\ \sin(\theta) & -\cos(\theta) \end{array} \right] $$ Is the following true: enter image description here Where "PERM" is an arbitrary 8x8 permutation matrix and $T$, $U$ and $S$ are 2x2 rotation matrices. "PERM", $T$, $U$ and $S$ could possibly depend on $R_\theta$ and $|\psi\rangle$.

More rigorously, is the following true: $$ (R_\theta \otimes I \otimes I)(TOFFOLI) |\psi\rangle = (P)(T \otimes U \otimes S) | \psi\rangle $$ Where $P$ is the arbitrary permutation matrix and the TOFFOLI gate is given as: $$ TOFFOLI = \left[ \begin{array}{cccccccc} 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 \end{array} \right] $$

If the input state, $|\psi\rangle$, were omitted, this relation would not in general be true, but what if $|\psi\rangle$ and $R_\theta$ are given? I am really only asking for a circuit that is equivalent when the input state, $|\psi\rangle$, is given.

If they are equivalent, what are $T$, $S$, $U$ and $P$? If they aren't equivalent, why not?

I would also be interested in the more general statement of whether there is an equivalence if the Toffoli gate is replaced by an arbitrary 8x8 permutation matrix but I would be satisfied with an answer to the above question.

I've thought about this for a bit but it gets complicated very quickly. I was hoping to see if anyone had any insight into whether this is possible or no.

I've been reading M. V. den Nest's paper "Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond", which can be found here

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Well, your Rθ is not a rotation but a reflection, but this difference is irrelevant to the answer. Also I will ignore the mathematical expression after “More riorously” because it does not correspond to the figure above it.

The answer is no, as shown by the following counterexample. Let θ be a real number in the range 0<θ<π/4, and let |φ⟩ = cosθ |0⟩ + sinθ |1⟩. Let |Ψ⟩ = |φ⟩ ⊗ |1⟩ ⊗ |φ⟩, and take gate R as the Hadamard gate H=Rπ/4. Then a straightforward calculation shows that the vector |Ψ′⟩ = (HII) Toffoli |Ψ⟩, when written in the standard basis, consists of exactly three nonzero coordinates (the |010⟩-, |011⟩-, and |110⟩-coordinates are nonzero). On the other hand, it is easy to see that when we write down the vector corresponding to a product state of more than one qubits in the standard basis, the number of nonzero coordinates must be a power of two, and this fact is not affected by applying a permutation matrix. Therefore, |Ψ′⟩ cannot be obtained by applying a permutation matrix to a product state.

share|improve this answer
    
Thanks for pointing out the flaw in the formula, this has been fixed. –  user4143 Dec 19 '11 at 16:18
    
Also, it looks like the right angle in the 'ket' isn't rendering properly. You might want to try using LaTex for formulas. –  user4143 Dec 19 '11 at 16:21
    
@user4143: To have this answer rendered correctly, you need a font which supports character U+27E9 (Mathematical Right Angle Bracket). I personally prefer to avoid MathJax because it seems like an unnecessarily complicated system. –  Tsuyoshi Ito Dec 20 '11 at 13:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.