Shor, I’ll do it
I’ve been talking a lot recently about how quantum algorithms don’t work. But last week JR Minkel, an editor at Scientific American, asked me to write a brief essay about how quantum algorithms do work, which he could then link to from SciAm‘s website.”OK!” I replied, momentarily forgetting about the quantum algorithm tutorials that are already on the web. So, here’s the task I’ve set for myself: to explain Shor’s algorithm without using a single ket sign, or for that matter any math beyond arithmetic.
Alright, so let’s say you want to break the RSA cryptosystem, in order to rob some banks, read your ex’s email, whatever. We all know that breaking RSA reduces to finding the prime factors of a large integer N. Unfortunately, we also know that “trying all possible divisors in parallel,” and then instantly picking the right one, isn’t going to work. Hundreds of popular magazine articles notwithstanding, trying everything in parallel just isn’t the sort of thing that a quantum computer can do. Sure, in some sense you can “try all possible divisors” — but if you then measure the outcome, you’ll get a random divisor, which almost certainly won’t be the one you want.
What this means is that, if we want a fast quantum factoring algorithm, we’re going to have to exploit some structure in the factoring problem: in other words, some mathematical property of factoring that it doesn’t share with just a generic problem of finding a needle in a haystack.
Fortunately, the factoring problem has oodles of special properties. Here’s one example: if I give you a positive integer, you might not know its prime factorization, but you do know that it has exactly one factorization! By contrast, if I gave you (say) a Sudoku puzzle and asked you to solve it, a priori you’d have no way of knowing whether it had exactly one solution, 200 million solutions, or no solutions at all. Of course, knowing that there’s exactly one needle in a haystack is still not much help in finding the needle! But this uniqueness is a hint that the factoring problem might have other nice mathematical properties lying around for the picking. As it turns out, it does.
The property we’ll exploit is the reducibility of factoring to another problem, called period-finding. OK, time for a brief number theory digression. Let’s look at my favorite sequence of integers since I was about five years old: the powers of two.
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …
Now let’s look at the powers of 2 “mod 15”: in other words, the remainder when 15 divides each power of 2.
2, 4, 8, 1, 2, 4, 8, 1, 2, 4, …
As you can see, taking the powers of 2 mod 15 gives us a periodic sequence, whose period (i.e., how far you have to go before it starts repeating) is 4. For another example, let’s look at the powers of 2 mod 21:
2, 4, 8, 16, 11, 1, 2, 4, 8, 16, …
This time we get a periodic sequence whose period is 6.
You might wonder: is there some general rule from which we could predict the period? Gee, I wonder if mathematicians ever thought of that question…
Well, duh, they did, and there’s a beautiful pattern discovered by Euler in the 1760’s. Let N be a product of two prime numbers, p and q, and consider the sequence
x mod N, x2 mod N, x3 mod N, x4 mod N, …
Then provided x is not divisible by p or q, the above sequence will repeat with some period that evenly divides (p-1)(q-1).
So for example, if N=15, then the prime factors of N are p=3 and q=5, so (p-1)(q-1)=8. And indeed, the period of the sequence was 4, which divides 8. If N=21, then p=3 and q=7, so (p-1)(q-1)=12. And indeed, the period was 6, which divides 12.
Now, I want you to step back and think about what this means. It means that, if we can find the period of the sequence
x mod N, x2 mod N, x3 mod N, x4 mod N, …
then we can learn something about the prime factors of N! In particular, we can learn a divisor of (p-1)(q-1). Now, I’ll admit that’s not as good as learning p and q themselves, but grant me that it’s something. Indeed, it’s more than something: it turns out that if we could learn several random divisors of (p-1)(q-1) (for example, by trying different random values of x), then with high probability we could put those divisors together to learn (p-1)(q-1) itself. And once we knew (p-1)(q-1), we could then use some more little tricks to recover p and q, the prime factors we wanted.
So what’s the fly in the ointment? Well, even though the sequence
x mod N, x2 mod N, x3 mod N, x4 mod N, …
will eventually start repeating itself, the number of steps before it repeats could be almost as large as N itself — and N might have hundreds or thousands of digits! This is why finding the period doesn’t seem to lead to a fast classical factoring algorithm.
Aha, but we have a quantum computer! (Or at least, we’re imagining that we do.) So maybe there’s still hope. In particular, suppose we could create an enormous quantum superposition over all the numbers in our sequence: x mod N, x2 mod N, x3 mod N, etc. Then maybe there’s some quantum operation we could perform on that superposition that would reveal the period.
The key point is that we’re no longer trying to find a needle in an exponentially-large haystack, something we know is hard even for a quantum computer. Instead, we’re now trying to find the period of a sequence, which is a global property of all the numbers in the sequence taken together. And that makes a big difference.
Look: if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you), there’s no feasible way to detect a single universe that’s different from all the rest. Such a lone voice in the wilderness would be drowned out by the vast number of suburb-dwelling, Dockers-wearing conformist universes. What one can hope to detect, however, is a joint property of all the parallel universes together — a property that can only be revealed by a computation to which all the universes contribute.
(Note: For safety reasons, please don’t explain the above to popular writers of the “quantum computing = exponential parallelism” school. They might shrivel up like vampires exposed to sunlight.)
So, the task before us is not hopeless! But if we want to get this period-finding idea to work, we’ll have to answer two questions:
- Using a quantum computer, can we quickly create a superposition over x mod N, x2 mod N, x3 mod N, and so on?
- Supposing we did create such a superposition, how would we figure out the period?
Let’s tackle the first question first. We can certainly create a superposition over all integers r, from 1 up to N or so. The trouble is, given an r, how do we quickly compute xr mod N? If r was (say) 300 quadrillion, would we have to multiply x by itself 300 quadrillion times? That certainly wouldn’t be fast enough, and fortunately it isn’t necessary. What we can do instead is what’s called repeated squaring. It’s probably easiest just to show an example.
Suppose N=17, x=3, and r=14. Then the first step is to represent r as a sum of powers of 2:
r = 23 + 22 + 21.
Then
Also, notice that we can do all the multiplications mod N, thereby preventing the numbers from growing out of hand at intermediate steps. This yields the result
314 mod 17 = 2.
OK, so we can create a quantum superposition over all pairs of integers of the form (r, xr mod N), where r ranges from 1 up to N or so. But then, given a superposition over all the elements of a periodic sequence, how do we extract the period of the sequence?
Well, we’ve finally come to the heart of the matter — the one part of Shor’s quantum algorithm that actually depends on quantum mechanics. To get the period out, Shor uses something called the quantum Fourier transform, or QFT. My challenge is, how can I explain the QFT to you without using any actual math? Hmmmm…
OK, let me try this. Like many computer scientists, I keep extremely odd hours. You know that famous experiment where they stick people for weeks in a sealed room without clocks or sunlight, and the people gradually shift from a 24-hour day to a 25- or 26- or 28-hour day? Well, that’s just ordinary life for me. One day I’ll wake up at 9am, the next day at 11am, the day after that at 1pm, etc. Indeed, I’ll happily ‘loop all the way around’ if no classes or appointments intervene. (I used to do so all the time at Berkeley.)
Now, here’s my question: let’s say I tell you that I woke up at 5pm this afternoon. From that fact alone, what can you conclude about how long my “day” is: whether I’m on a 25-hour schedule, or a 26.3-hour schedule, or whatever?
The answer, of course, is not much! I mean, it’s a pretty safe bet that I’m not on a 24-hour schedule, since otherwise I’d be waking up in the morning, not 5pm. But almost any other schedule — 25 hours, 26 hours, 28 hours, etc. — will necessarily cause me to “loop all around the clock,” so that it’d be no surprise to see me get up at 5pm on some particular afternoon.
Now, though, I want you to imagine that my bedroom wall is covered with analog clocks. These are very strange clocks: one of them makes a full revolution every 17 hours, one of them every 26 hours, one of them every 24.7 hours, and so on for just about every number of hours you can imagine. (For simplicity, each clock has only an hour hand, no minute hand.) I also want you to imagine that beneath each clock is a posterboard with a thumbtack in it. When I first moved into my apartment, each thumbtack was in the middle of its respective board. But now, whenever I wake up in the “morning,” the first thing I do is to go around my room, and move each thumbtack exactly one inch in the direction that the clock hand above it is pointing.
Now, here’s my new question: by examining the thumbtacks in my room, is it possible to figure out what sort of schedule I’m keeping?
I claim that it is possible. As an example, suppose I was keeping a 26-hour day. Then what would happen to the thumbtack below the 24-hour clock? It’s not hard to see that it would undergo periodic motion: sure, it would drift around a bit, but after every 12 days it would return to the middle of the board where it had started. One morning I’d move the thumbtack an inch in this direction, another morning an inch in that, but eventually all these movements in different directions would cancel each other out.
On the other hand — again supposing I was keeping a 26-hour day — what would happen to the thumback below the 26-hour clock? Here the answer is different. For as far as the 26-hour clock is concerned, I’ve been waking up at exactly the same time each “morning”! Every time I wake up, the 26-hour clock is pointing the same direction as it was the last time I woke up. So I’ll keep moving the thumbtack one more inch in the same direction, until it’s not even on the posterboard at all!
It follows, then, that just by seeing which thumbtack travelled the farthest from its starting point, you could figure out what sort of schedule I was on. In other words, you could infer the “period” of the periodic sequence that is my life.
And that, basically, is the quantum Fourier transform. Well, a little more precisely, the QFT is a linear transformation (indeed a unitary transformation) that maps one vector of complex numbers to another vector of complex numbers. The input vector has a nonzero entry corresponding to every time when I wake up, and zero entries everywhere else. The output vector records the positions of the thumbtacks on the posterboards (which one can think of as points on the complex plane). So what we get, in the end, is a linear transformation that maps a quantum state encoding a periodic sequence, to a quantum state encoding the period of that sequence.
Another way to think about this is in terms of interference. I mean, the key point about quantum mechanics — the thing that makes it different from classical probability theory — is that, whereas probabilities are always nonnegative, amplitudes in quantum mechanics can be positive, negative, or even complex. And because of this, the amplitudes corresponding to different ways of getting a particular answer can “interfere destructively” and cancel each other out.
And that’s exactly what’s going on in Shor’s algorithm. Every “parallel universe” corresponding to an element of the sequence contributes some amplitude to every “parallel universe” corresponding to a possible period of the sequence. The catch is that, for all periods other than the “true” one, these contributions point in different directions and therefore cancel each other out. Only for the “true” period do the contributions from different universes all point in the same direction. And that’s why, when we measure at the end, we’ll find the true period with high probability.
Obviously there’s a great deal I’ve skipped over; see here or here or here or here or here or here or here or here or here or here or here or here for details.
Follow
Comment #1 February 24th, 2007 at 5:40 am
Great article Scott! But it leaves one vital question unanswered: is it known whether the number of quantum algorithm tutorials on the web is larger or smaller than the number of string theory vacua?
PS. The live preview feature on this blog is way cool! What software is this?
Comment #2 February 24th, 2007 at 6:19 am
Thanks, Jeremy!
No, I don’t think sgn(|{tutorials}|-|{vacua}|) is known.
I use WordPress, and recently installed a plugin called Live Comment Review after several people requested it.
Comment #3 February 24th, 2007 at 6:36 am
Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen.
Comment #4 February 24th, 2007 at 6:49 am
Thanks, Peter!
Comment #5 February 24th, 2007 at 8:39 am
[…] Scott Aaronson over at Shtetl-optimized recently posted a great description of Shor’s algorithm for non-specialists, in response to a request from JR Minkel, a Scientific American writer. Even though Scott has an alarming lack of musical taste he has few peers when it comes to describing complex technical issues to non-specialists. […]
Comment #6 February 24th, 2007 at 9:03 am
congrats, Scott. With you I can really learn something!
(of course, it’s desirable I can read the original papers with “real” math and stuff, but someday I’ll get there.)
Comment #7 February 24th, 2007 at 9:48 am
Scott, I’m really a man on the street, and I can attest that your explanation is great!
The only catch is: it looks like this period-finding method can be also used with respect to SAT problem. Please tell me where the following reasoning breaks down and why.
Consider boolean expression P of n variables. Generally, it can be satisfied with some values, and these solutions don’t have a structure we can exploit. However, if we consider another expression P1=Q & P, where Q is also a boolean expression of n variables, which we select in such a way that it’s ALWAYS true, and then apply our quantum computation to P1, then we will have a period of exactly 2^n in case P has solutions, and period of 1 otherwise. I assume there’s a way of distinguishing between 2^n and 1, so it seems that we solved SAT.
What am I missing here?
Comment #8 February 24th, 2007 at 9:54 am
you should go to bed on time you naughty computer scientists
Comment #9 February 24th, 2007 at 9:58 am
Sorry, I forgot one important thing: Q doesn’t contain any variables occurring in P, of course.
Comment #10 February 24th, 2007 at 10:16 am
P1 = Q & P
Q === true
therefore P1 = P
?
Comment #11 February 24th, 2007 at 10:37 am
Hi Vasily,
Good question. The period-finding algorithm doesn’t work for a function that’s 0 almost everywhere, and 1 only in a few exponentially-far-apart places. For the quantum Fourier transform to tell you anything useful, you need a function whose periodic structure is “globally detectable.” There’s a paper by Hales and Hallgren from years ago where they made that intuition more precise.
Best,
Scott (in Toronto airport)
Comment #12 February 24th, 2007 at 10:41 am
Hi Vasily,
You seem a lot smarter than the typical man on the street, to come up with the catch. What you’re missing is something that Scott glossed over in his simplified explanation. The difficulty is that the quantum period-finding algorithm only works if most of the values of periodic function (over its period) are different. In your example, they’re all the same. However, you have to look at the details of the algorithm to figure this out.
Comment #13 February 24th, 2007 at 11:45 am
You win one free Internet.
Comment #14 February 24th, 2007 at 12:12 pm
^^^
Internets
Comment #15 February 24th, 2007 at 12:22 pm
What a great description. Thank you!
Comment #16 February 24th, 2007 at 1:34 pm
Great explanation of everything except the Fourrier. I too am at least 2/3rds of a man on the street in that I’ve long forgotten the equations behind most of the theoretical ideas.
I am convinced however that a Fourrier transform has an easier explanation. I will admit that you tie your example well into the flow of the article, but still… I will brood about it, and try to come back to your blog for more info…
Comment #17 February 24th, 2007 at 3:26 pm
[…] MEGA C00L LINK: Scott Aaronson wrote a superb article on quantum factoring algorithm. […]
Comment #18 February 24th, 2007 at 3:29 pm
About the 2^n period vs. 1-period question by Vasily: I think the problem is that in the example Vasily gave the string actually HAS a period 1 – “almost”. The only places where P(i) isn’t equal P(i+1) is when i or i+1 is a solution of P. We may assume are extremely rare (otherwise a random attempt would find a satisfying assignment). The quantum fourier transform cannot tell if we have an exact period or an almost-exact one. In the same way, a quantum fourier algorithm cannot distinguish if the period of the string is k or 2k for example, if there are only very few locations in the string where the k period fails to hold, even of the 2k period always holds.
Comment #19 February 24th, 2007 at 6:13 pm
[…] The man on the street that Shor has seen Scott Aaronson explains Shor’s algorithm here in an article that Shor himself describes as “the best job of explaining quantum computing to the man on the street that I’ve seen”. Word. Also, see the previous post in which Aaronson summarizes a recent breakthrough in quantum algorithms that will potentially allow a single ant to evaluate a NAND tree in O(√N) time. […]
Comment #20 February 24th, 2007 at 8:33 pm
Great Article! And indeed, I’m also a man on the street in quantum computing … but I tried hard to understand your conclusion and yes, I think, I succeeded a little bit. 😉
Thx, hope to read more of you soon.
Comment #21 February 24th, 2007 at 8:36 pm
That’s what I feared: Scott’s explanation was TOO GOOD to be true…
I know I’m allowed to ask just one question at a time, and this space is not commutative 🙂 So, my next question:
When we are talking about periodic function (in factorization algorithm), we should really have a function y=f(x), where x is ORDERED: if we randomly reshuffle set of x values (which is 0, 1, 2,… 2^N), we will destroy the picture. How can we force 2^N universes respond in the right order?
Comment #22 February 24th, 2007 at 9:19 pm
Jonathan, you remark helps to clarify things a bit. Can I reformulate it like this: if we ask quantum computer “Is it likely that you have a period of 2^n?”, the answer will be “Yes” regardless of whether we have accidental “ones” here and there or not – because f(x) and f(x+2^n) will almost always be both zeros (for every x). Is this correct?
Comment #23 February 24th, 2007 at 10:36 pm
Vasily, I’ll try to elaborate a bit on the basic problem that the quantum fourier transrofm can solve. Given a string, define f(p) to be the probability that string(x)=string(x+p) where x is a random location in the string. This is a number between 0 and 1. It is 1 when p is a perfect period of the string. The quantum fourier transform will actually answer you a *random* p, BUT – the probability it will answer a specific p is proportional to f(p). In your case f(p) is almost 1 regardless of the value of p – since the function is almost always zero, string(x) and string(x+p) will both be zero most of the time). So the quantum computer will just answer a random p between 1 and 2^n and you get no information from this. On the other hand, of some string has period 3000, but nothing less than that, the quantum computer will answer a random p among all p’s divisible by 3000 (because 3000,6000,9000,…3000*k are all periods of the string), because in all other places f(p) is almost zero. This behavior enables you to extract the original period of 30 00 (can you see why?).
By the way, the point is that a quantum computer can find this period without knowing it in advance. Given some potential period p you can test how good is p as a period of a string without a quantum computer, simply by sampling some random values x and checking whether string(x)=string(x+p). The strength of the quantum computer is being able to find this p among the huge number of potential periods (p can be any value between 1 and 2^n). In the idea you suggested you already knew the hopeful period in advance so there is little hope a quantum computer will help anyway. Your problem is that you are want to distinguish between f(p) being exactly 1 versus f(p) being 0.9999999…, which you cannot do even on a quantum computer.
This turned out to be kind of long – let me know if it helped you at all.
Comment #24 February 25th, 2007 at 5:53 am
Jonathan: yes, this helps, just one question remains: what if instead of values 0 and 1, we have values 0 and B, where B is really huge – maybe, it will affect the result somehow?
Comment #25 February 25th, 2007 at 8:32 am
This line is confusing:
That means that you’re excited that you’re able to learn something about the prime factors of N, and not that you’re talking about N!, right? I guess it doesn’t make any sense to talk about the prime factors of a factorial, which is why it’s confusing when it shows up there out of nowhere.
Comment #26 February 25th, 2007 at 10:29 am
Obviously, this is an exclamation mark, not a factorial. Should have been preceded by backslash: N\! 🙂
Comment #27 February 25th, 2007 at 11:11 am
yes, this helps, just one question remains: what if instead of values 0 and 1, we have values 0 and B, where B is really huge – maybe, it will affect the result somehow?
In quantum computing, there is more structure than just probabilities. Nonetheless, quantum computing does reduce to probabilities at certain times, and probabilities still have to be between 0 and 1. That’s because an event cannot occur less than none of the time nor more than all of the time. Jonathan’s “f(p)” referred to a probability.
Comment #28 February 25th, 2007 at 12:42 pm
Greg, I understand that. I asked about values, not probabilities. Logical expression evaluates either to 0, or to 1. In SAT, we are considering the case when there’s only a small number of ones – we can’t detect them. The idea is: although ones are few and far between, maybe they can shout louder if we multiply them by large factor? Maybe it’s a stupid question, though.
Comment #29 February 25th, 2007 at 1:14 pm
Vasily,
In Shor’s period-finding algorithm, you already assume that the periodic function is 1-to-1 within each period, so that the values of the hiding function f are completely distinguishable. Distinguishability of values is indeed the only way to “shout as loud as possible”. Indeed, the algorithm doesn’t even really examine the values, it throws them away. The information that it has left is a partial measurement of the quantum state of the input to f.
As Scott referenced, there has been some analysis of how well Shor’s algorithm continues to work if f is not completely 1-to-1 on the period, i.e. on Z/p. Basically it still works provided that f is not nearly periodic with some other period. I am not completely sure, but I think that it can still happen even if f is Boolean-valued, provided that the sequence of values is sufficiently “textured” that it is statistically far away from other periods.
However, if f is a “periodic needle of 1s in a haystack of 0s”, i.e. if there is only a single 1 in the entire period, then it’s bad. On the one hand, you are already as loud as possible with this structure — you could for example be less loud if if the values of f were quantum states that are only partly distinguishable. On the other hand, every integer is a near period: For any q, f(x) = f(x+q) for virtually all values of x. In this case, Shor’s algorithm has no hope, indeed you are back to the theorem that the quantum computer cannot extract enough information about f without exponentially many evaluations, regardless of how well it examines the queries.
Comment #30 February 25th, 2007 at 3:28 pm
Thanks Greg, Jonathan and others, I’m satisfied with your answers. Now back to another major problem I have – problem of ordering (see my post at 8:36 pm Feb 24). Please.
Comment #31 February 25th, 2007 at 3:59 pm
Vasily,
From a strict information-theoretic point of view, any ordering of the values of x will do, provided that the calling quantum computing knows what they are. Because, if the hiding function is f and the ordering is g, the computer can apply Shor’s algorithm to the composition f circ g^{-1}. However, the ordering could itself be difficult to compute. If there is any ordering whatsoever and the computer has to guess what it is, then that clearly destroys all information about the period.
Reordering the domain of a periodic function is one indication that there is no simple characterization of what a quantum computer can do, just like the situation for classical computers. All existing algorithms of either kind are only examples.
Comment #32 February 25th, 2007 at 4:33 pm
To Vasily:
About the ordering – like you noted, ordering is EVERYTHING. It is exactly the difference between a “structured” problem that may be solvable and an “unstructured” one that cannot be solved.
Example:
Solvable: Given string of length 2^n, does it have a period of length at most 2^n/2?
Probably unsolvable: Given a string, is it a random shufle of the string I just mentioned? In the first case you know the “1”‘s in the string appear in specific places – multiples of the period. In the second string all you know is that you have some 1’s in the string, with no apparent order, so you’re back to the SAT-like situation.
How do we “force” the order on the universes? You may think of it this way – in each of the 2^n universes write a unique number “x” between 1 and 2^n. Then in each universe compute F(x) in this universe, but preserve the x. This way the universe remembers both x and F(x), and all other algorithms can use this information, so the order (“structure”) is preserved, and you can go proceed and compute periods.
Comment #33 February 25th, 2007 at 4:48 pm
Greg, your explanation is a little fuzzy. (Maybe, some hermitian transformation can be applied to it to make things straight, but I’m lacking required skills yet :)). Maybe, we can gradually unravel it? First off, I don’t understand how we can talk about periodic functions is domain is unordered. The best you can do with unordered domain is to count distinct function values, which is certainly not the goal of this algorithm. Maybe, you can come up with some metaphor (like Scott did with the clocks)? Or, simpler, maybe there’s a way to find some mathematical analogy, or whatever – not necessarily 100% rigorous, but we can add fine print later (again, like in the previous problem). Please think about that.
Comment #34 February 25th, 2007 at 5:00 pm
Jonathan, thanks, I understand. Short question: when we are talking about periodic functions, we imagine something like sinus, with several waves, so we can easily see the pattern. In factorization algorithm for N=p*q, you have a period which is almost as big as N, it differs by just approx 2*SQRT(N) – so, it’s like one wave plus just a tiny portion of the second wave. Is there enough information there to figure out that one period ended and the next one started? Or the picture is artificially appended with more periods (like I so unsuccessfully tried with SAT)?
Comment #35 February 25th, 2007 at 6:31 pm
Learned & witty expositions of quantum information theory like Scott’s are not my bag (an old school expression deriving from the Norse baggi ), but to assist those who attempt them, here is a artist’s foresighted description of QM:
@inCollection{Borges:49, author = {J. L. Borges}, title = {The Other Death}, booktitle = {The Aleph and Other Stories}, publisher = {Penguin Classics}, year = 1949, note = {(italics in the original): “The Summa Theologica denies that God can undo, unmake, what once existed, but it says nothing about the tangled concatenation of causes and effects—which is so vast and so secret that not a single remote event can be annulled, no matter how insignificant, without canceling the present. To change the past is not to change a mere single event; it is to annul all its consequences, which extent to infinity. In other words: it is to create two histories of the world.”},}
Oh yeah, the reference to O.N. baggi is a joke, but the BibTeX entry is accurate. Enjoy the Academy Awards, everyone ! 🙂
Comment #36 February 25th, 2007 at 10:56 pm
Thanks for writing about Shor’s algorithm in a comprehsible (to a layman) way. I suppose hearing it straight from Peter Shor is as good as it gets, but maybe it doesn’t hurt to hear us laypersons say it too.
Comment #37 February 26th, 2007 at 4:43 am
Using the analogy of the thumb-tacks on the wall, the measurement procedure is to draw a line from the origin to the final position of the thumbtack, then draw a square, the side of which is the line you’ve just drawn. Repeat for each of the N clocks and sum up all the areas of the squares. The quantum computer gives you the answer ‘clock i’ according to the formula.
Prob(i) = Area(i) / Area(1)+Area(2)+….+Area(N)
You point out that the thumb tack representing the right answer heads off in a constant direction and makes a big square compared to the wrong answers that dance around the origin, but your example has only three clocks.
If you are dealing with Shor’s algorithm applied to factor large numbers, ie. trying to factor a 512 binary digit number as would be useful for cryptography, there would presumably be N=2^512 clocks.
It seems there are now a lot of ‘wrong’ answers compared to a few ‘right’ answers, and each wrong answer still contributes a small random amount to the denominator, reducing P(i).
My question is: (why) do the right answers continute to dominate as the number of clocks considered goes up, and how does this scale with the number of digits used?
Comment #38 February 26th, 2007 at 5:47 am
+ to Richard’s question: “wrong” arrows may not cancel out completely: if it’s a random walk, we still have a non-zero sum = approx. SQRT(nSteps) – so, really, how the algorithm filters out this “noise”, and what is the accuracy of period computation?
Comment #39 February 26th, 2007 at 6:16 am
My question is: (why) do the right answers continute to dominate as the number of clocks considered goes up, and how does this scale with the number of digits used?
Obviously, this is one of the main questions Shor had to answer in the analysis of his algorithm.
The short answer is that you can get the true period with constant probability, after a constant number of repetitions. For the long answer, read one of the references I linked to.
Comment #40 February 26th, 2007 at 9:06 am
Vasily, remember the period value is some DIVISOR of (p-1)(q-1), which will have order at most sqrt(N) and not N-sqrt(N), so you have many repetitions of the period.
Comment #41 February 26th, 2007 at 10:14 am
Jonathan, thanks. Well, “at most sqrt(N)” is an overkill either, but it depends on our choice of x (that’s what I missed). For some x, period can be as big as (p-1)(q-1), if x is primitive both modulo p and modulo q, but these values are really rare. But remember, in RSA they select p and q in such a way that both p-1 and q-1 have very big prime factors (and even if they didn’t specify this explicitly, this would be the case automatically – that’s the way how things are). So, period is hardly sqrt(N), but apparently small enough for the algorithm to work.
Comment #42 February 26th, 2007 at 12:09 pm
I don’t understand how we can talk about periodic functions is domain is unordered.
My answer was confusing because I didn’t know what you were asking. I am not sure what sort of computational problems you are considering for functions with unstructured domains and targets. But, generally speaking, such problems are variously in AM, NP, and SZK. (I don’t know of any examples that are in BQP but not BPP.) It is easy to suppose that the smallest of these, SZK, is somehow “close” to BQP, or conceivably even a subset. However, Scott has a blog post that explains there is an oracle that places SZK outside of BQP.
In factorization algorithm for N=p*q, you have a period which is almost as big as N, it differs by just approx 2*SQRT(N) – so, it’s like one wave plus just a tiny portion of the second wave.
Actually, in Shor’s algorithm you have to do the QFT on a width of order N^2 or greater, so that you obtain many periods. But my main answer to your questions is that resistance is futile, you will be assimilated. You should obtain a copy of Nielsen and Chuang and learn Shor’s algorithm for real.
Comment #43 February 26th, 2007 at 1:52 pm
Greg, of course, you are right, I have to read the source; prior to that, I have to read Nielsen and Chuang; prior to that, I need to refresh all math (matrices, complex analysis, etc), get some elementary introduction to QM, think hard about it, read it again, repeat N times – this is true. However, this is not realistic for me at the moment (maybe, after retirement, if I live long enough). For now, I have very modest goal: to get some rough idea of what these quantum computers are capable of – and thanks to Scott, you, Jonathan and others – I really have a feeling that I learnt something from this discussion. And maybe, it’s close to maximum one can get without dedicating his entire life to this subject.
One major issue that still bothers me is accuracy. Nothing is 100% – perfect, and you probably can’t get this period with absolute accuracy (if you can, it may constitute a greater breakthrowgh than the algorithm itself). But nothing short of near-absolute perfection suffices here: if your error is just (10^-6)% relative to the value of period, you don’t seem to gain much: if you cope with 512-bit numbers, they will increase the size to 1024, and you will have to improve accuracy exponentially. Since technological improvements might be exponentially hard, is it possible that instead of exponent in one place we get it in another?
Comment #44 February 26th, 2007 at 3:13 pm
Greg, of course, you are right, I have to read the source; prior to that, I have to read Nielsen and Chuang
Actually, you don’t strictly have to read the source. Peter Shor’s papers are completely reasonable, but Nielsen and Chuang has a complete review of Shor’s algorithm.
One major issue that still bothers me is accuracy.
It still bothers a lot of people, but (a) it is not directly an algorithm question, and (b) there are many proposed solutions. The point is that quantum computing is a probabilistic model — quantum probability is a generalization of standard probability — applied to a finite-state computer. Just as with classical probabilities, a large probability of a small error is equivalent to a small probability of a large error; errors are essentially discrete (*). You can therefore develop a theory of quantum error correction. Quantum error correction is far more difficult in practice than classical error correction, and is central to the question of whether quantum computing is realistic. Nonetheless, error correction becomes a separate topic from algorithms in quantum computing, just as it does in non-quantum computing. Algorithms are only inseparable from error in analog computing (and sometimes in numerical analysis, which is simulated analog computing); quantum computing is not really that.
(*) For example, if you have a bit which is supposed to be 1 with probability 1/2, but it is actually 1 with probability 3/5, then you can equivalently say that the bit is wrong with probability 1/10. There is a similar principle for qubits.
Comment #45 February 26th, 2007 at 3:24 pm
[…] Shtetl-Optimized » Blog Archive » Shor, I’ll do it (tags: algorithms cryptography programming quantum science) […]
Comment #46 February 26th, 2007 at 4:32 pm
As usual, Scott, your explanation is first-class (not that you needed me to say so, with Peter chiming in!). I actually understand the number-theoretic bit of Shor’s algorithm now. I wasn’t completely convinced by the period-finding discussion, though… so I had the hubris to think I could proffer an alternative explanation. You know, for, like, physicists… with oscillators and stuff. So… here goes:
———————-
Scott asked, “…But then, given a superposition over all the elements of a periodic sequence, how do we extract the period of the sequence?”
Really, there are two questions here. First, suppose I’ve got a periodic data sequence. How do I extract the period? Second (this is the interesting bit) if the sequence is a quantum state, how do I use quantum mechanics to do it really fast?
The answer to question #1 is “Use something called the Fourier transform,” and the answer to question #2 is “Use the quantum Fourier transform”. Of course, this is nothing but jargon, so lemme explain what it means.
Like me, you probably spent some quality time on the swing set as a kid. Maybe (like me) you tried to swing so hard that you went all the way around (no, I didn’t succeed). You probably discovered that, to really get going, you have to push in synch with your swing. Every swing has a natural period — say, 5 seconds. If it’s got a 5-second period, and you kick your legs really fast (say, every 1 second) or really slow (say, every 17 seconds), then you never really get going. On the other hand, if you kick every 5 seconds exactly, then you can get up some serious oomph — even if the kicks are weak.
That swing is like a canary in a coal mine. It detects periodic kicks. Just by seeing how high you go, a bystander can tell whether your kicks are coming at 5-second periods. There’s nothing sacred about 5 seconds — we can design swings with 3-second periods, 13-second periods, or whatever.
So, if I use my data sequence as a sequence of kicks, then one swing with a period of T tells me, “Does the data repeat with period T?” What if I don’t know what N is, and I want to find it? Well, imagine a whole array of swings, each tuned to a different period (T=1,2,3…N). If I kick all of them (at once) with my data sequence, then the one that swings the highest at the end is the correct period.
This, mon frere, is what the Fourier transform does. It simulates all those swings. You put in an N-element sequence, and it spits out a different N-element sequence — containing the heights to which N different swings get pumped up. The F.T. is a linear transform — feed it the sum of two sequences, you get the sum of their F.T.s — which means it can be represented as an N x N matrix. (I should point out that a quantum operation on log(N) qubits is also represented as an N x N matrix… which is sort of suggestive.)
Does the Fourier transform solve our factoring problem? Nope. See, N is really big — as big as the number we want to factor. So just writing down that sequence would take a loooonnng time. Furthermore, the Fourier transform takes O(N log(N)) steps, which is even slower than just sequentially dividing by every prime number less than N.
However, the F.T. provides a bunch of extraneous information. We get the heights of all N swings, whereas we only want to know which one goes the highest. This is where quantum mechanics gets useful! If we had a quantum state with N amplitudes — each proportional to the height of a swing — then it would be Very Useful. Why? Because a measurement would single out one swing, and a swing’s probability-of-being-observed is proportional to [the square of] its amplitude. So if one swing is much much higher than the others — i.e., the initial sequence was periodic only at that swing’s period — then we’ll see it in short order.
The Q.F.T makes this state. It’s an algorithm on log(N) qubits that turns the initial state (the periodic sequence) into the Very Useful state (whose amplitude has a spike at the period). It only takes O( log(N) ) operations, which is possible because we only need O( log(N) ) qubits to store the initial and final states. This is how Shor’s algorithm finds the period of a sequence.
—————
I don’t think I made any serious mistakes in there. I think it’s fascinating to see how the QFT works, because it sort of does something (a Fourier transform) much faster than classical algorithms — but at the cost of giving you much less information. The classical F.T. tells you the amplitude of all the swings… whereas the Q.F.T basically only tells you if one (or a few) of the swings is swinging higher than all the rest combined. So you gotta have a problem with lots of structure to attack it this way.
Comment #47 February 26th, 2007 at 5:03 pm
WOW
Comment #48 February 26th, 2007 at 5:54 pm
Excuse me for the question that might be stupid: does the whole thing takes advantage of the fact that transforms in quantum mechanics and F.T. are both based on sin/cos (whatever that means), and plays with double meaning of these sin/cos?
Comment #49 February 26th, 2007 at 7:14 pm
Robin’s swing analogy is much clearer than the clock/thumbtack one, IMO. No offense, Scott, as you did a wonderful job with the rest of the article. Maybe you should incorporate Robin’s analogy if you ever decide to revise your article!
Comment #50 February 26th, 2007 at 7:43 pm
Scott, thanks for posting this. I’m still working on my post with the link you mentioned—lest anyone think I left you hanging. Blogging isn’t supposed to be real-time, is it?
Comment #51 February 26th, 2007 at 7:46 pm
By the way, here http://eprint.iacr.org/2005/051.ps is a way to factor N when it is the product of two large primes (RSA primes) by finding the period of not just any random number, but Scott’s favorite number, 2!
Comment #52 February 26th, 2007 at 7:46 pm
[…] Scott factors while Terrance Tao discusses some quantum mechanics based on…Tomb Raider! […]
Comment #53 February 26th, 2007 at 9:41 pm
[…] cueing up ‘Quantum computers cannot solve NP-complete problems in polynomial time.’ — Shor, I’ll do it … its getting late … and its getting hard to think straight … (maybe impssible in curved space-time). We’ll have to pick it up at some [random] later time. In the meanwhile … the Shtetl-Optimized motto leaves a lot to be desired/discussed. It presumes the existence of: […]
Comment #54 February 27th, 2007 at 8:53 am
Hi Scott,
Very nice article. I think we in theoretical computer science will certainly benefit a lot from having more people like you.
Comment #55 February 28th, 2007 at 10:41 am
The discussion on this topic is very enjoyable.
Feynman’s (relatively) little-known book QED: The Strange Theory of Light and Matter uses arrows-head-to-tail as a physical model of quantum superposition, and thereby avoids using any equations at all (if memory serves) to explain all of quantum electrodynamics.
Comment #56 March 1st, 2007 at 11:35 am
[…] […]
Comment #57 March 1st, 2007 at 1:37 pm
Scott, gotta say, to incorporate Prof. Shor into the title of your post is a really nice show of respect for one of your fellow computing experts. Come to think of it, you oughta consider retaining this title “Shor, I’ll do it” when you publish this essay in “Scientific American.” If nothing at all, the title has a nice ring to it!
Although my words don’t carry much weight–if not–any weight at all, I must remark that this piece on quantum algorithms is–far and away–the best one I’ve had the pleasure of coming across so far… 😉
Once again, thanks for sharing!
Comment #58 March 1st, 2007 at 2:00 pm
Thanks, Cynthia! But the piece of mine that’s going to appear in Scientific American is a different one — sorry for the confusion!
Comment #59 March 3rd, 2007 at 3:01 am
Thanks a lot, Scott. I’m just a science enthusiast with little to no knowledge of the mathematics that are usually necessary to understand serious explanations on quantum computing… but I find your post most enlightning.
I think the clocks’ example is brilliant, I like it even more than the swingers’ one; maybe some got lost because of the personal references about schedules shifts (which I’m pretty familiar with) or the explanations on the experiment with the dark room; but it seemed to me a classic example of indirect measuring (or maybe I got it all wrong! hahaha).
Sorry for the long, non-contributing comment, thanks again.
Comment #60 March 4th, 2007 at 3:26 pm
[…] Shtetl-Optimized » Blog Archive » Shor, I’ll do it (tags: quantum.computing quantum.mathematics mathematics science shor quantum.theory quantum.algorithm) […]
Comment #61 March 6th, 2007 at 1:27 am
[…] QED Filed under: Computing, Geek, Technology — McBaine @ 5:22 am Here’s a well written but succint article on a singular tenet of quantum computing called Shor’s Algorithm. The concept of parallel computing through quantum computers is an idea that has been expressed by a number of authors in the scientific community, but as Aaronson clearly demonstrates its not quite an accurate description of what takes place. Read it here. […]
Comment #62 March 6th, 2007 at 7:12 am
My question is, will a quantum computer be self-aware?
nature has already built the most powerful computer we know of, actually nature has already built everything we are discovering, from jet engines in bacteria, to video cameras (eyes).
is it possible that nature has already made a quantum computer also?
I have heard that one way to build a quantum computer would be with a mass of plasma and a magnetic field.
I can think of a pretty complex one already. The sun. The star that sits just 93 million miles away from our planet.
if our sun is like a quantum computer, is it also plausible that our sun is actually aware of its surroundings and is also aware of us?
Now i am not one for religion, but to it is way more plausible that the sun is intelligent and is aware of us like we are aware of bacteria than there is a GOD who is omnipotent who knows everything and created the whole universe.
Comment #63 March 10th, 2007 at 1:29 pm
sab says: Nature has already built the most powerful computer we know of, actually nature has already built everything we are discovering
The technologies found in nature include most of “the classics”: radar, wheels, levers, fire, catalysts, networks, aircraft, refrigerators.
A major exception is the class of quantum coherent technologies that includes masers and lasers, magnetic resonance imaging, and their offspring quantum computation.