3
$\begingroup$

Following up on this question, can someone help me clear up the notation we're using for states in Shor's algorithm? It's very unclear what the sentence "where the second register is $|1\rangle$ made from $n$ qubits" in the Wikipedia article means. The input state is supposedly $|0\rangle^{\otimes 2n+1} \otimes |1\rangle$. The first register makes sense, and one could write $|0\rangle^{\otimes 2n+1}=|\underbrace{0 \ldots 0}_{2n+1}\rangle$. Would one say that's $|0\rangle$ made from $2n+1$ qubits?

It appears we have states for all integers $0 \le k < 2^n$, which makes sense because if our fundamental qubit states are $|0\rangle$ and $|1\rangle$ then we can write $k$ in binary and we have $2^n$ tensor product states. Isn't the state $|0\rangle = |\underbrace{0 \ldots 0}_{n}\rangle$ and $|1\rangle = |1\underbrace{0 \ldots 0}_{n-1}\rangle$?

Clearly there must be $n$ qubits in the second register as input since $U$ (multiplication by $a$ modulo $N$) is a $2^n \times 2^n$ matrix. Yes, $U$ has eigenvectors, and $|1\rangle$ is an equal sum of those eigenvectors, but that doesn't help me understand the fixed input state.

$\endgroup$

1 Answer 1

3
$\begingroup$

They mean that the second register uses $n$ qubits, and it's in the state $|1\rangle$.

This is using the standard way of enumerating the $2^n$ possible (computational basis) $n$-qubit states, so $|k\rangle$ denotes the $n$-qubit state corresponding to the binary string which in base-10 corresponds to $k\in\mathbb{N}$.

Consider for example $n=2$. Then $$|0\rangle \simeq|0,0\rangle, \quad |1\rangle \simeq|0,1\rangle, \quad |2\rangle \simeq|1,0\rangle, \quad |3\rangle \simeq|1,1\rangle.$$ So more generally, you could say that $|1\rangle$ denotes the $n$-qubit state with binary representation $|0\rangle^{\otimes(n-1)}\otimes|1\rangle$. Although this expression is generally not very insightful in this context.

Note also that conventions may vary, and so you might have the equivalence $|1\rangle\simeq|1\rangle\otimes|0\rangle^{\otimes(n-1)}$ rather than the one above. This doesn't affect any result of course, it's only a notational detail.

The reason you use this particular state for the second register is that, as you might observe directly, the modular multiplication operator $U_a$ has eigenvectors $|u_s\rangle$, corresponding to eigenvalues $e^{2\pi i s/p}$ with $p$ period, which sum to precisely $|1\rangle$. Therefore using $|1\rangle$ as second register is a convenient way to perform a quantum phase estimation with a set of possible eigenstates of $U_a$ in superposition.

$\endgroup$
5
  • $\begingroup$ Okay cool, I think we’re saying more or less the same thing. Thanks, this clears up my confusion. $\endgroup$ Sep 26 at 1:41
  • $\begingroup$ I am a little bit unsure about you answer. In Shor algorithm we have $n$ qubits initialized to state $|0\rangle$ used for saving a period and $m$ qubits initialized to state $|1\rangle$ to which result of a modular exponential is saved. If I understand your answer correctly, it should always hold $m=1$? On Wiki I see that the second register is multi-qubit, not only one quantum bit. What am I missing? $\endgroup$ Sep 26 at 17:39
  • 1
    $\begingroup$ @MartinVesely I agree that the second $m$-qubit register starts on the state $|1\rangle$; but I'd disagree that the $m$ qubits are initialized in the state $|1\rangle$. These are very different statements. For period finding we want the former, because we need a state that is a balanced sum of (some of) the eigenstates of $U_a$. You can also see it in the Wikipedia page when they compute the sum of the $|\psi_k\rangle$ and get $|1\rangle$. There you don't get $|1\rangle\equiv |1\rangle^{\otimes m}$, you get the $m$-qubit state corresponding to the binary decomposition of $1\in{\Bbb Z}$. $\endgroup$
    – glS
    Sep 26 at 18:34
  • $\begingroup$ @glS: Thanks for explanation. Notation could be sometimes tricky. $\endgroup$ Sep 27 at 6:26
  • $\begingroup$ @glS I really think $|1\rangle = |1\rangle \otimes |0\rangle^{\otimes (n-1)}$ is so much clearer. We're distinguishing between $1 \in \mathbb{Z}$ and $1 \in \{0,1\}$, integer and binary 1. When I actually built the circuit in Qiskit, you see clearly that you initialize the second register to all $|0\rangle$'s and put an $X$ gate only on the first bit, which flips it to a 1. $\endgroup$ Sep 27 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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