4 ms·

I'll oversimplify my question, how will be possible for us to get useful information from a system based in randomness? For my understanding, I can ask a quant

by elboru 13y ago

I'll oversimplify my question, how will be possible for us to get useful information from a system based in randomness? For my understanding, I can ask a quantum system: is this a cow? and it'll answer: 1. Yes 2. No 3. 72

libraryatnight 13y ago
This was my question too, I don't understand how you can begin to make a computer out of something with - as they explained - intrinsic randomness. And I didn't quite understand, how, if we can't see or ask the computer how it did something, how we can be certain of its answer or know that we've built something that does what we want.
- takeoutweight 13y ago
  You can know the probability that the algorithm will output the correct answer. If the probability of a correct response is > 50%, all you have to do is run the algorithm multiple times to get within, say, 99.99% certainty that the most-commonly reported answer is correct.
  - libraryatnight 13y ago
    Thank you, this makes sense
geuis 13y ago
The video really doesn't do a good job of explaining how a quantum computer can work. They just hit the basic high points because this video is intended for a general rather than specific audience. A qubit exists in multiple states until measured. When you entangle multiple qubits together, each one increases the power of the system exponentially. Quantum computers are only good for certain kinds of problems like factoring large prime numbers. Luckily quantum systems are good at things classic computers aren't, and vice versa. You have to state your "question" in such a way that it causes the overall state of the quantum system to resolve on your answer. I know my answer isn't much better. I only have a high level understanding with none of the math behind it. There's good videos if you search and watch a few times to get the concepts. I can't remember the exact scenario that was explained to me, but it was something like this. Imagine the Traveling Salesman problem. You want the best route. But with a regular computer, it might take thousands of years to calculate the best route. With a quantum computer, if you structure the measurement correctly (this is how you "program" a quantum computer) then only the best route is what the system decoheres to. There was also something about light and how if you had the right filter, only the answer gets through. I really forgot the details of that one, but maybe it'll help.
- flebron 13y ago
  Pfft, anyone can factor large prime numbers :)
  - kefka 13y ago
    I can do it right now, for ANY arbitrary large prime P. .......thinking.... P and 1 are the factors!
- ssivark 13y ago
  To substantiate your point: Essentially, quantum computing is useful for problems that could take help from a large degree of parallelization. Quantum mechanics has an inherent parallelization at it heart. Otoh, simulating that amount of parallelization with classical resources will be exponentially complex.
  - takeoutweight 13y ago
    This is a VERY common misconception, and is not a good intuition for how quantum computing is different than classical. A better intuition, in my opinion, is computing with "un-flipped" coins, except with funny complex-valued probabilities of heads vs tails instead of real values between 0.0 and 1.0. Because the probabilities are complex-valued, they interact in ways that can seem a bit counter-intuitive, (it makes sense it is counter-intuitive, because how many quantities do we deal with day-to-day that are described with complex numbers?) These interactions can provide some algorithmic speed up on some nicely structured problems. It's not always obvious what these problems are, and it doesn't relate to do whether the problem is highly-parallel. My intuition for "quantum-friendly" is if a problem involves some kind of periodicity, or Fourier-like frequency analysis, then perhaps you'll see a quantum speedup. But it's important to remember the coins don't somehow "try every flip possible" to find the answer you're looking for -- if they did that you'd be able to solve NP problems in constant time.
    - ssivark 13y ago
      I agree that the superposition with complex probability amplitudes (fundamental quantum randomness) is different from just statistical randomness of trying every possibility. I fact, this is one of the notions which is being used to verify whether the D-Wave computer (as a black box) is "truly quantum". 1. I don't quite see what periodicity has to do with the speedup. Could you elaborate on that? 2. "...if they did that you'd be able to solve NP problems in constant time." Again, please explain. In QM, the answer you calculate is actually the weighted sum over all possibilities... so the way I see it, it does cover every possible path. That answer might not be useful in telling you which is the shortest single path, but if you were an electron traversing a graph and wanted to optimize your travel, you'd do exactly what the quantum computer says and traverse all paths! The classical notion of "best path" might be trickier to deduce from a quantum computer. Maybe I'm addressing something tangential to what you're saying.
Strilanc 13y ago
Quantum computing is sortof like... destructively interfering all the non-solutions so the only likely measurement results are solutions. The state of the computer is a vector of complex amplitudes (one entry per possible answer, n qubits -> 2^n possible answers). The operations of the computer correspond to unitary matrix multiplications against the state vector. An entry's probability of being the result is the squared length of its final amplitude. I try to explain it better here: http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm http://twistedoakstudios.com/blog/Post2644_grovers-quantum-s...
- valtron 13y ago
  The visualization for complex product is amazing!
ssivark 13y ago
Haven't seen the video yet, but I'll take a shot at your question. To my knowledge, the original motivation of a "quantum computer" was to simulate quatum mechanical systems (leading back to Feynman's lectures on computation). Simulating quantum (or other kinds of random) events with classical resources (conventional computers) is a hard problem in the sense that it's exponentially more complex than a classical problem. Conversely, a quatum computer is very useful to solve such problems, think of: genetic algorithms, Monte-Carlo, etc. It is expected to do way better than classical computers. That doesn't necessarily make the simple problems easy on a quantum computer. Asking it the sort of question you did is not a measure of it's usefulness. Since I'm not an expert on this, my aswer might be a little loose, but that's the basic idea.

by elboru 13y ago

libraryatnight 13y ago

This was my question too, I don't understand how you can begin to make a computer out of something with - as they explained - intrinsic randomness. And I didn't quite understand, how, if we can't see or ask the computer how it did something, how we can be certain of its answer or know that we've built something that does what we want.

takeoutweight 13y ago
You can know the probability that the algorithm will output the correct answer. If the probability of a correct response is > 50%, all you have to do is run the algorithm multiple times to get within, say, 99.99% certainty that the most-commonly reported answer is correct.
- libraryatnight 13y ago
  Thank you, this makes sense

geuis 13y ago

The video really doesn't do a good job of explaining how a quantum computer can work. They just hit the basic high points because this video is intended for a general rather than specific audience. A qubit exists in multiple states until measured. When you entangle multiple qubits together, each one increases the power of the system exponentially. Quantum computers are only good for certain kinds of problems like factoring large prime numbers. Luckily quantum systems are good at things classic computers aren't, and vice versa. You have to state your "question" in such a way that it causes the overall state of the quantum system to resolve on your answer. I know my answer isn't much better. I only have a high level understanding with none of the math behind it. There's good videos if you search and watch a few times to get the concepts. I can't remember the exact scenario that was explained to me, but it was something like this. Imagine the Traveling Salesman problem. You want the best route. But with a regular computer, it might take thousands of years to calculate the best route. With a quantum computer, if you structure the measurement correctly (this is how you "program" a quantum computer) then only the best route is what the system decoheres to. There was also something about light and how if you had the right filter, only the answer gets through. I really forgot the details of that one, but maybe it'll help.

flebron 13y ago
Pfft, anyone can factor large prime numbers :)
- kefka 13y ago
  I can do it right now, for ANY arbitrary large prime P. .......thinking.... P and 1 are the factors!
ssivark 13y ago
To substantiate your point: Essentially, quantum computing is useful for problems that could take help from a large degree of parallelization. Quantum mechanics has an inherent parallelization at it heart. Otoh, simulating that amount of parallelization with classical resources will be exponentially complex.
- takeoutweight 13y ago
  This is a VERY common misconception, and is not a good intuition for how quantum computing is different than classical. A better intuition, in my opinion, is computing with "un-flipped" coins, except with funny complex-valued probabilities of heads vs tails instead of real values between 0.0 and 1.0. Because the probabilities are complex-valued, they interact in ways that can seem a bit counter-intuitive, (it makes sense it is counter-intuitive, because how many quantities do we deal with day-to-day that are described with complex numbers?) These interactions can provide some algorithmic speed up on some nicely structured problems. It's not always obvious what these problems are, and it doesn't relate to do whether the problem is highly-parallel. My intuition for "quantum-friendly" is if a problem involves some kind of periodicity, or Fourier-like frequency analysis, then perhaps you'll see a quantum speedup. But it's important to remember the coins don't somehow "try every flip possible" to find the answer you're looking for -- if they did that you'd be able to solve NP problems in constant time.
  - ssivark 13y ago
    I agree that the superposition with complex probability amplitudes (fundamental quantum randomness) is different from just statistical randomness of trying every possibility. I fact, this is one of the notions which is being used to verify whether the D-Wave computer (as a black box) is "truly quantum". 1. I don't quite see what periodicity has to do with the speedup. Could you elaborate on that? 2. "...if they did that you'd be able to solve NP problems in constant time." Again, please explain. In QM, the answer you calculate is actually the weighted sum over all possibilities... so the way I see it, it does cover every possible path. That answer might not be useful in telling you which is the shortest single path, but if you were an electron traversing a graph and wanted to optimize your travel, you'd do exactly what the quantum computer says and traverse all paths! The classical notion of "best path" might be trickier to deduce from a quantum computer. Maybe I'm addressing something tangential to what you're saying.

Strilanc 13y ago

Quantum computing is sortof like... destructively interfering all the non-solutions so the only likely measurement results are solutions. The state of the computer is a vector of complex amplitudes (one entry per possible answer, n qubits -> 2^n possible answers). The operations of the computer correspond to unitary matrix multiplications against the state vector. An entry's probability of being the result is the squared length of its final amplitude. I try to explain it better here: http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm http://twistedoakstudios.com/blog/Post2644_grovers-quantum-s...

valtron 13y ago
The visualization for complex product is amazing!

ssivark 13y ago

Haven't seen the video yet, but I'll take a shot at your question. To my knowledge, the original motivation of a "quantum computer" was to simulate quatum mechanical systems (leading back to Feynman's lectures on computation). Simulating quantum (or other kinds of random) events with classical resources (conventional computers) is a hard problem in the sense that it's exponentially more complex than a classical problem. Conversely, a quatum computer is very useful to solve such problems, think of: genetic algorithms, Monte-Carlo, etc. It is expected to do way better than classical computers. That doesn't necessarily make the simple problems easy on a quantum computer. Asking it the sort of question you did is not a measure of it's usefulness. Since I'm not an expert on this, my aswer might be a little loose, but that's the basic idea.