4 ms·

I still need to gain the intuition for why a quantum computer can operate on some kinds of things "faster". I've read some of the math, but that did little to s

I still need to gain the intuition for why a quantum computer can operate on some kinds of things "faster". I've read some of the math, but that did little to satisfy me (I need to study it more clearly). But all of this seems in a tragic state at the moment. Allowing rampant misinformation and hype as to what these machines are actually capable of.

msclrhd 8y ago
It's not that they can execute a computation faster in the traditional sense. It is that you can exploit the quantum behaviour in some types of computation (e.g. factoring primes) to make the answer more probable, and thus more likely to be "observed", when you read the state of the quantum computer and thus make it easy to locate the correct answer compared to traditional algorithms. PBS Infinite Series has several videos on quantum computing and Shor's algorithm: 1. https://www.youtube.com/watch?v=IrbJYsep45E https://www.youtube.com/watch?v=IrbJYsep45E "The Mathematics of Quantum Computers" 2. https://www.youtube.com/watch?v=12Q3Mrh03Gk https://www.youtube.com/watch?v=12Q3Mrh03Gk "How to Break Cryptography" 3. https://www.youtube.com/watch?v=wUwZZaI5u0c https://www.youtube.com/watch?v=wUwZZaI5u0c "Hacking at Quantum Speed with Shor's Algorthm"
krastanov 8y ago
If you are specifically interested in building up the mathematical intuition, check out "Quantum Computing since Democritus" by Aaronson - it excels at presenting the intuition. For less comp-sci and more physics look at the standard references: Nielsen and Chuang's book and Preskill's lecture notes.
- nixpulvis 8y ago
  Thanks for the links. I'll start here: http://www.theory.caltech.edu/%7Epreskill/ph219/index.html#lecture http://www.theory.caltech.edu/%7Epreskill/ph219/index.html#l... and probably get the books too (hey, they're cheap on amazon... god I hate myself).
  - krastanov 8y ago
    The Aaronson book is mostly available on his academic website as lecture notes.
jcranmer 8y ago
I'm going to butcher a lot of the physics here, but here's the gist of it that should avoid some quantum myths: The quantum state of a system is not described by a simple real probability but by a complex number. This means that there is an additional degree of freedom that you can adjust in a quantum state that doesn't change its probability of occurring. The nature of entanglement means that there is constructive and destructive interference when you go through certain quantum operations. Traditionally, a quantum word can be thought of as being a probability distribution over the various possible values of the word. You can build quantum gates that act like classical gates on the binary values, and it's this property that often causes people to describe a quantum computer as executing every possibility in parallel. The difficulty is that the result you get is sampled by the probability distribution, which means you need some sort of interference between the results to allow you to boost the probability of picking the answer you want. A quantum speedup is only possible when you can find the interference. In the case of Shor's algorithm (for factoring), the interference is basically a quantum variant on FFT; in the case of Grover's algorithm (finding x such that f(x) = y), the interference is something that redistributes the probabilities among a plane of the sphere.
- nixpulvis 8y ago
  OK, yes. This builds on the parts of my intuition that already exist. It's about building a system (from combinations of quantum operators) that maximizes the probability distribution of the result you want. I'm still unsure of the timeline of any quantum operator, and the "finding the interference" seems equivalent to saying something like "find the function" or something more classical.
  - msclrhd 8y ago
    With Shor's algorithm, the quantum part of the algorithm comes down to finding the period of 'a mod N' where N is the prime number you have, and a is a number less than N that is not a factor of N. Here, the period is the smallest value of x where 'a^x mod N = 1'. This is done applying the Quantum Fourier Tranform on each 'a^x mod N' using x+1 complex roots of unity for that value of x. You can visualise this as x+1 arrows from the centre of a unit circle with an angle 2pi/(x+1). So, for x=3 you have 4 arrows pointing up, down, left, and right. When you stack the arrows end to end, they will loop back to their starting point (3 will form a triangle, 4 a square, etc.). The key is that when multiplting this quantum fourier transform with the value of 'a^x mod N', the 1s (at the period) will occur at the same point around the unit circle only for the cases where the number of complex roots is a multiple of the period. This has the effect that for the correct answer, the arrows are lined up together in a single direction, amplifying the number and thus the probability of selecting that number. For the others, the arrows cycle and loop back on each other, so stay fairly small, decreasing the probability they will be selected.
Jach 8y ago
Scott's book referenced is very good, but you might also want to see if his layman's blog explanation of Shor's Algorithm is useful to you: https://www.scottaaronson.com/blog/?p=208 https://www.scottaaronson.com/blog/?p=208
- nixpulvis 8y ago
  This was quite good at filling in some intuition.
deleted 8y ago
[deleted]
catpolice 8y ago
There's a lot of misinformation in this space, so be careful who you listen to. I hope to say as few false things as possible, but I can offer no guarantees. One source of confusion is that there are different types of proposed quantum computers. Some, like the D-wave machines, use stochastic measurement processes to arrive at probably-correct solutions. This is called "annealing", and it's a lot like what many machine learning algorithms do to try and find global minima in error function spaces, only the quantum mechanics gives it an edge in not getting stuck in local minima for various reasons. These aren't universal computers - they only implement very specialized algorithms in a kind of abstract sense. It's sort of like how if you take a box of different sized rocks and shake it for a while, you'll eventually find that the small rocks have made their way to the bottom and the bigger rocks have drifted to the top (this is called granular convection). There's a sense in which this is like a search algorithm that helps you find the biggest rocks. The quantum version of this (very loosely speaking) would be if the rocks sorted themselves faster because the small rocks would sometimes just tunnel through the big rocks. Using quantum effects to speed up annealing lets you do annealing faster than a classical simulation - but most problems aren't annealing problems. So present day quantum computers are specialized machines that do a kind of computation using quantum effects, but they can't run general purpose quantum algorithms. Think of them like co-processor chips that aren't quite CPUS. That said, it's sort of hard to define what a general purpose quantum computer would even be (for various reasons), so maybe that's unfair. Anyway, D-wave machines can't run Shor's algorithm, which is one of the examples of the "exponential speedup" over classical computation. The (claimed) algorithmic efficiency of quantum computing as it applies to quantum algorithms has to do with how much computation is done in each step. We represent information in physical systems and process that information by making those physical systems interact in a way that affects a state space transformation. The amount of processing we can do in "one step" depends on the size of the state space of our data representation and the kinds of operations we can affect via physical interactions. Conventional computation involves a bunch of parallel systems that have 2 distinguishable states interacting pairwise through networks of logic gates that perform a limited number of transformations. Systems of qubits have many more than 2^N distinguishable states (technically, an infinite number), and operations on them can be arbitrary linear transformations. So each quantum logic gate can do a lot more computation than a classical binary gate. Quantum algorithms basically translate information in the limited classical state space to the bigger quantum state space, do fancy operations, then project back into the classical space. It's sort of like data parallelism in the sense that if you can do a series of small operations or one big SIMD operation, the latter will generally be faster. Operations on qubits make use of physical parallelism that's only possible in the much bigger non-classical state space.

msclrhd 8y ago

It's not that they can execute a computation faster in the traditional sense. It is that you can exploit the quantum behaviour in some types of computation (e.g. factoring primes) to make the answer more probable, and thus more likely to be "observed", when you read the state of the quantum computer and thus make it easy to locate the correct answer compared to traditional algorithms. PBS Infinite Series has several videos on quantum computing and Shor's algorithm: 1. https://www.youtube.com/watch?v=IrbJYsep45E https://www.youtube.com/watch?v=IrbJYsep45E "The Mathematics of Quantum Computers" 2. https://www.youtube.com/watch?v=12Q3Mrh03Gk https://www.youtube.com/watch?v=12Q3Mrh03Gk "How to Break Cryptography" 3. https://www.youtube.com/watch?v=wUwZZaI5u0c https://www.youtube.com/watch?v=wUwZZaI5u0c "Hacking at Quantum Speed with Shor's Algorthm"

krastanov 8y ago

If you are specifically interested in building up the mathematical intuition, check out "Quantum Computing since Democritus" by Aaronson - it excels at presenting the intuition. For less comp-sci and more physics look at the standard references: Nielsen and Chuang's book and Preskill's lecture notes.

nixpulvis 8y ago
Thanks for the links. I'll start here: http://www.theory.caltech.edu/%7Epreskill/ph219/index.html#lecture http://www.theory.caltech.edu/%7Epreskill/ph219/index.html#l... and probably get the books too (hey, they're cheap on amazon... god I hate myself).
- krastanov 8y ago
  The Aaronson book is mostly available on his academic website as lecture notes.

jcranmer 8y ago

I'm going to butcher a lot of the physics here, but here's the gist of it that should avoid some quantum myths: The quantum state of a system is not described by a simple real probability but by a complex number. This means that there is an additional degree of freedom that you can adjust in a quantum state that doesn't change its probability of occurring. The nature of entanglement means that there is constructive and destructive interference when you go through certain quantum operations. Traditionally, a quantum word can be thought of as being a probability distribution over the various possible values of the word. You can build quantum gates that act like classical gates on the binary values, and it's this property that often causes people to describe a quantum computer as executing every possibility in parallel. The difficulty is that the result you get is sampled by the probability distribution, which means you need some sort of interference between the results to allow you to boost the probability of picking the answer you want. A quantum speedup is only possible when you can find the interference. In the case of Shor's algorithm (for factoring), the interference is basically a quantum variant on FFT; in the case of Grover's algorithm (finding x such that f(x) = y), the interference is something that redistributes the probabilities among a plane of the sphere.

nixpulvis 8y ago
OK, yes. This builds on the parts of my intuition that already exist. It's about building a system (from combinations of quantum operators) that maximizes the probability distribution of the result you want. I'm still unsure of the timeline of any quantum operator, and the "finding the interference" seems equivalent to saying something like "find the function" or something more classical.
- msclrhd 8y ago
  With Shor's algorithm, the quantum part of the algorithm comes down to finding the period of 'a mod N' where N is the prime number you have, and a is a number less than N that is not a factor of N. Here, the period is the smallest value of x where 'a^x mod N = 1'. This is done applying the Quantum Fourier Tranform on each 'a^x mod N' using x+1 complex roots of unity for that value of x. You can visualise this as x+1 arrows from the centre of a unit circle with an angle 2pi/(x+1). So, for x=3 you have 4 arrows pointing up, down, left, and right. When you stack the arrows end to end, they will loop back to their starting point (3 will form a triangle, 4 a square, etc.). The key is that when multiplting this quantum fourier transform with the value of 'a^x mod N', the 1s (at the period) will occur at the same point around the unit circle only for the cases where the number of complex roots is a multiple of the period. This has the effect that for the correct answer, the arrows are lined up together in a single direction, amplifying the number and thus the probability of selecting that number. For the others, the arrows cycle and loop back on each other, so stay fairly small, decreasing the probability they will be selected.

Jach 8y ago

Scott's book referenced is very good, but you might also want to see if his layman's blog explanation of Shor's Algorithm is useful to you: https://www.scottaaronson.com/blog/?p=208 https://www.scottaaronson.com/blog/?p=208

nixpulvis 8y ago
This was quite good at filling in some intuition.

deleted 8y ago

[deleted]

catpolice 8y ago

There's a lot of misinformation in this space, so be careful who you listen to. I hope to say as few false things as possible, but I can offer no guarantees. One source of confusion is that there are different types of proposed quantum computers. Some, like the D-wave machines, use stochastic measurement processes to arrive at probably-correct solutions. This is called "annealing", and it's a lot like what many machine learning algorithms do to try and find global minima in error function spaces, only the quantum mechanics gives it an edge in not getting stuck in local minima for various reasons. These aren't universal computers - they only implement very specialized algorithms in a kind of abstract sense. It's sort of like how if you take a box of different sized rocks and shake it for a while, you'll eventually find that the small rocks have made their way to the bottom and the bigger rocks have drifted to the top (this is called granular convection). There's a sense in which this is like a search algorithm that helps you find the biggest rocks. The quantum version of this (very loosely speaking) would be if the rocks sorted themselves faster because the small rocks would sometimes just tunnel through the big rocks. Using quantum effects to speed up annealing lets you do annealing faster than a classical simulation - but most problems aren't annealing problems. So present day quantum computers are specialized machines that do a kind of computation using quantum effects, but they can't run general purpose quantum algorithms. Think of them like co-processor chips that aren't quite CPUS. That said, it's sort of hard to define what a general purpose quantum computer would even be (for various reasons), so maybe that's unfair. Anyway, D-wave machines can't run Shor's algorithm, which is one of the examples of the "exponential speedup" over classical computation. The (claimed) algorithmic efficiency of quantum computing as it applies to quantum algorithms has to do with how much computation is done in each step. We represent information in physical systems and process that information by making those physical systems interact in a way that affects a state space transformation. The amount of processing we can do in "one step" depends on the size of the state space of our data representation and the kinds of operations we can affect via physical interactions. Conventional computation involves a bunch of parallel systems that have 2 distinguishable states interacting pairwise through networks of logic gates that perform a limited number of transformations. Systems of qubits have many more than 2^N distinguishable states (technically, an infinite number), and operations on them can be arbitrary linear transformations. So each quantum logic gate can do a lot more computation than a classical binary gate. Quantum algorithms basically translate information in the limited classical state space to the bigger quantum state space, do fancy operations, then project back into the classical space. It's sort of like data parallelism in the sense that if you can do a series of small operations or one big SIMD operation, the latter will generally be faster. Operations on qubits make use of physical parallelism that's only possible in the much bigger non-classical state space.