Skip to main content

Questions tagged [order-finding]

For questions about the order-finding problem.

Filter by
Sorted by
Tagged with
3 votes
1 answer

Why is the operator $M_a |x\rangle= |a \cdot x \pmod{N} \rangle $ unitary?

If $N\geq 2$, $a\in \mathbb{Z}_N$, and $a^r= 1$ for some $r$. Consider the operator $M_a$, which is related to order finding : $M_a |x\rangle= |a \cdot x \pmod{N} \rangle $ if $x\in \mathbb{Z}_N$ What ...
metaUser's user avatar
1 vote
0 answers

Eigenvalues of a unitary U that implements a periodic function [closed]

What can be said about the eigenvalues of a unitary quantum gate $U$ which implements $f(x)=f(x+r) \forall x$, as in $U|x\rangle|0\rangle\rightarrow|x\rangle|f(x)\rangle$ ? The reason I'm asking is ...
user27293's user avatar
2 votes
2 answers

In the order finding circuit, why is the equal superposition of the controlled unitary eigenstates the $|1\rangle$ state?

In Nielsen and Chuang's "Quantum Computation and Quantum Information" when the quantum order finding process is being presented (specifically page 227, equation 5.44) we are told that by &...
Gabe Richardson's user avatar
1 vote
0 answers

Probability of the case when $r'\neq r$ and $r'$ is a factor $r$ in the order finding algorithm

In the Order-Finding algorithm it is stated that it might be that $s$ and $r$ have a common factor, in which case the number $r'$ returned by the continued fractions algorithm be a factor of $r$, and ...
Sooraj S's user avatar
  • 831
5 votes
1 answer

Cost of Modular Exponentiation in Shor's algorithm

In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as $$ U|y\rangle=|xy\;(\mod N)\rangle\text{ ...
Sooraj S's user avatar
  • 831
4 votes
1 answer

Understanding the 3rd step of Nielsen and Chuang's description of the quantum order-finding algorithm

In Nielsen and Chuang's description of Quantum order-finding algorithm, the 3rd step of the procedure says $$\frac1{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|x^j\mod N\rangle \approx \frac1{\sqrt{r2^t}}\...
Guangliang's user avatar
4 votes
1 answer

Application of QFT to Order-finding

In the Nielsen & Chuang book, section 5.3.1 page 226, there is a statement which goes like this:- (statement-1) The quantum algorithm for order-finding is just the phase estimation algorithm ...
user27286's user avatar
  • 975