<p>The problem stems from the fact that your understanding of quantum computing (as outlined in the question) is incorrect. Certainly quantum computers are poorly explained in most popularizations. A quantum computer cannot simply check if a solution exists within a superposition deterministically, let alone in unit time.</p>

<p>The most general representation of the quantum state of $n$ qubits is the $2^n \times 2^n$ <a href="http://en.wikipedia.org/wiki/Density_matrix">density matrix</a> $\rho$, where the diagonal entries correspond to the probability of finding the system in a particular classical state, and the off diagonal entries indicate the phase of the superposition (going to 0 for classical probability distributions). </p>

<p>Any quantum algorithm can be seen as a unitary operation followed by some measurement in the computational basis. Given an initial input state $\rho$, it will evolve to $\rho&#39; = U\rho U^\dagger$. The most general set of measurements that can be performed are called <a href="http://en.wikipedia.org/wiki/POVM">positive operator valued measurements</a>(POVMs), where each measurement outcome $i$ is associated with a positive sei-definite Hermitian operator $P_i$ and the probability of outcome $i$ is given by $p_i = \mbox{Tr}(P_i \rho)$ (and hence $\sum_i P_i = \mathbb{I}$).</p>

<p>Within these constraints the operations you describe simply are not possible.</p>

CC BY-SA 3.0
2012-04-15T11:14:24.670Z
OK, so my naive assumption (the third bullet point) was simply wrong! Thanks :)
Ronald
CC BY-SA 3.0
2012-04-15T11:59:23.850Z
Yes, both the 3rd and 4th points are wrong.
Joe Fitzsimons
CC BY-SA 3.0
2012-04-15T12:07:16.227Z
Thanks, accepted your answer! It has become clear that I have some research to do.
Ronald
CC BY-SA 3.0
2015-05-17T04:36:12.303Z
Actually the very first bullet point, "a qubit acts as though it is in both states at once (1 and 0)", is already wrong for all practical purpose.   See this article by me in Slate:  http://www.slate.com/blogs/future_tense/2012/10/22/david_wineland_serge_haroche_even_the_nobel_foundation_press_release_mischaracterized.html
Greg Kuperberg
CC BY-SA 3.0
2012-04-14T17:10:33.487Z
2012-04-14T17:10:33.487Z
Joe Fitzsimons
<p>I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media. </p>

<p>So, I'm hoping that somebody will be able to help me to correct my understanding of quantum computing.</p>

<p>My understanding is as follows:</p>

<ul>
<li>a qubit acts as though it is in both states at once (1 and 0)</li>
<li><p>a register of n qubits can act as though it is in any of $2^n$ states.</p></li>
<li><p>this has obvious benefits in terms of a factoring algorithm: we can identify whether any of these states is a 'correct' solution to a problem.</p></li>
<li><p>however, I understand that although we can identify whether or not there is a correct state, we can not necessarily observe the state which is correct</p></li>
</ul>

<p>So, my assumption up to now has been that we can 'pin' one or more of the qubits by replacing with a classical bit, and observe whether or not the remaining set of states still contain a correct solution. (Simple!)</p>

<p>My problem is that this would seem to lead to a solution to the factoring problem in $O(log n)$ time, by passing down and pinning each of the bits. I haven't proved that out but it feels right, based on my assumptions.</p>

<p>However, Shor's algorithm takes $O((logn)^3)$ and doesn't seem that simple. I'd like to know which of my assumptions are wrong, but Wikipedia's description of Shor's algorithm seems intractable to me.</p>

<p>Can you help identify my misconception? Which of my points of understanding are correct/incorrect?
Thanks!</p>

CC BY-SA 3.0
2012-04-14T18:07:26.450Z
There's a great blog post by Scott Aaronson explaining Shor's algorithm in non-specialist terms: http://www.scottaaronson.com/blog/?p=208
arnab
<quantum-computing><big-picture><factoring>
Layman Interpretation: Quantum Factoring Algorithm
Ronald
# Layman Interpretation: Quantum Factoring Algorithm

(Asked by: username_0 on 2012-04-14)

I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media.

So, I'm hoping that somebody will be able to help me to correct my understanding of quantum computing.

My understanding is as follows:

* a qubit acts as though it is in both states at once (1 and 0)
* a register of n qubits can act as though it is in any of $2^n$ states.
* this has obvious benefits in terms of a factoring algorithm: we can identify whether any of these states is a 'correct' solution to a problem.
* however, I understand that although we can identify whether or not there is a correct state, we can not necessarily observe the state which is correct

So, my assumption up to now has been that we can 'pin' one or more of the qubits by replacing with a classical bit, and observe whether or not the remaining set of states still contain a correct solution. (Simple!)

My problem is that this would seem to lead to a solution to the factoring problem in $O(log n)$ time, by passing down and pinning each of the bits. I haven't proved that out but it feels right, based on my assumptions.

However, Shor's algorithm takes $O((logn)^3)$ and doesn't seem that simple. I'd like to know which of my assumptions are wrong, but Wikipedia's description of Shor's algorithm seems intractable to me.

Can you help identify my misconception? Which of my points of understanding are correct/incorrect?
Thanks!

**Tags:** quantum-computing, big-picture, factoring

> **Comments:**
> **username_1**: There's a great blog post by Scott Aaronson explaining Shor's algorithm in non-specialist terms: http://www.scottaaronson.com/blog/?p=208  

---

## 1 answers

### Answer by username_2 on 2012-04-14. Score: 11 | Accepted answer

The problem stems from the fact that your understanding of quantum computing (as outlined in the question) is incorrect. Certainly quantum computers are poorly explained in most popularizations. A quantum computer cannot simply check if a solution exists within a superposition deterministically, let alone in unit time.

The most general representation of the quantum state of $n$ qubits is the $2^n \times 2^n$ [density matrix](http://en.wikipedia.org/wiki/Density_matrix) $\rho$, where the diagonal entries correspond to the probability of finding the system in a particular classical state, and the off diagonal entries indicate the phase of the superposition (going to 0 for classical probability distributions).

Any quantum algorithm can be seen as a unitary operation followed by some measurement in the computational basis. Given an initial input state $\rho$, it will evolve to $\rho' = U\rho U^\dagger$. The most general set of measurements that can be performed are called [positive operator valued measurements](http://en.wikipedia.org/wiki/POVM)(POVMs), where each measurement outcome $i$ is associated with a positive sei-definite Hermitian operator $P\_i$ and the probability of outcome $i$ is given by $p\_i = \mbox{Tr}(P\_i \rho)$ (and hence $\sum\_i P\_i = \mathbb{I}$).

Within these constraints the operations you describe simply are not possible.

> **Comments:**
> **username_0**: OK, so my naive assumption (the third bullet point) was simply wrong! Thanks :)  
> **username_2**: Yes, both the 3rd and 4th points are wrong.  
> **username_0**: Thanks, accepted your answer! It has become clear that I have some research to do.  
> **username_3**: Actually the very first bullet point, "a qubit acts as though it is in both states at once (1 and 0)", is already wrong for all practical purpose.   See this article by me in Slate:  http://www.slate.com/blogs/future_tense/2012/10/22/david_wineland_serge_haroche_even_the_nobel_foundation_press_release_mischaracterized.html  

---

