5 ms·

The First Universal Quantum Processor

53 points by TravisLS 17y ago

lionheart 17y ago
I'm curious, what kinds of application ideas exist that are possible on quantum computers that aren't on regular computers?
- amichail 17y ago
  Factoring is possible in polynomial time.
  - dave_au 17y ago
    From what I can remember, Schors algorithm gives you a polynomial speedup for factoring rather than putting it in polynomial time. It's been a little while since I was up to speed on this though.
  - lionheart 17y ago
    See, I've heard this before. But it really doesn't mean anything to most people. The only concrete example I can think of is cracking modern encryption. Does anybody have any ideas that would be useful to everyday life? I'm 100% sure that there are a ton.
    - deleted 17y ago
      [deleted]
    - rdtsc 17y ago
      Well unless users work for NSA, are somehow aware of encryption algorithms, are concerned about protecting their data, or are interested in factoring large numbers, this would not interest them much. Grover's search algorithm however, will speedup searching. It would be possible to search very large databases in a much shorter time : O(sqrt(n)) instead of O(n). Of course, many problems are based on searching so it is hard to enumerate all the possible end-user visible effects of this.
      - fauigerzigerk 17y ago
        What about the data that is searched? Where would it be stored for a quantum computer to access it without losing all the speedup on IO?
        rdtsc 17y ago
        Idealy only an index would be searched. For example when a sorting algorithm is presented, typically we assume that items are just integers. So if the database itself is huge, one would take a column and feed that into the quantum computer along with a matching function and a search item and the output would be the position of the item in the column. In general it is assumed that 'items' are integers. That is general enough. But since no practical implementations exist, still we still don't know how it would work in the real world with a real database. Here is a more in depth (and somewhat dramatic) explanation: For N, items to be search, it would take log2(N) qubits (that's enough to represent all N states). The matching function would have to be a quantum gate/operator. In other words, matching is performed in the quantum world. The idea behind quantum algorithms is to encode the input in a set of qubits, then make them interact in a way that creates a superposition of states. A superposition of states can be thought of as sending the input into a 'magic' quantum world, where N qubits simoultaneously represent all 2^N binary states. Then a set of quantum operators (gates) are applied to the state vector, while it is still in this magic quantum world. All is fine and dandy (provided that we can mentain the whole quantum world in a stable/isolated state). Then the 'sad' part is that once we measure the result and bring it into the 'real' world, the whole 'magic' quantum world collapses on itself, and only one particular state out of 2^N emerges. The trick is then to apply the quantum operators such that the probability of the quantum world collapsing to one particular 2^N state is increased. In case of Grover's algorithm that is what happens. The quantum operators increase the probability of the quantum state collapsing to the matched index. It is a probabilistic algorithm in the sense that it might have to be run a couple of times. EDIT: removed stupid spelling errors
    - korch 17y ago
      You can use polynomial time factoring to prove P = NP. Which means you have simultaneously solved a ton of outstanding optimization problems in science and engineering, and would allow for the creation of AI, clean renewable energy and practical space travel. Obviously those innovations would lead to the biggest change in the history of human civilization, and probably would cause lasting world peace. All from something as "useless" as factoring integers. True story.
- nearestneighbor 17y ago
  If time is not a constraining factor, then none (Turing-completeness). Applications requiring much parallelism, like NP-complete problems, may be more amenable to being solved by quantum computers in the future.
- RiderOfGiraffes 17y ago
  Breaking RSA, and most (all?) current forms of crypto used on the 'net.
- JulianMorrison 17y ago
  These are uses I recall from a recent lecture on QC: Using "adiabatic" qbits (not like this one), it seems you can solve any problem that can be structured as a low energy state. Examples of these are: PCB track routing, city planning, some kinds of pattern matching search in large datasets such as gene maps. There are possible applications to AI because it can efficiently update a neural network or a Bayes net. Also (not sure what kind of qbits are best for this) you should be able to simulate a quantum-influenced process, such as protein folding, one for one rather than via exhaustive calculation on supercomputers. Factoring crypto is often cited, but to be honest it's a very boring application compared to the many others.
- rdtsc 17y ago
  Theoretically none. Quantum computers are universal Turing machines. The main advantage of quantum computers is speedup. 5 years ago (when I took a couple of courses in QC) there were basically 2 quantum algorithms -- Shor's factorization and Grover's search. The former speeds up integer factorization (and discrete logarithm) and brings it to polynomial time, and the later speeds up search from O(n) to O(sqrt(n)). So just being able to quickly factor integers breaks a lot of encryption algorithms, and a faster search would really help with data processing. One of the main difficulty with quantum computers is quantum de-coherence. Qubits when they are entangled must be isolated from the outside environment until the final result measurement is taken. That is what is preventing the creation of large, multi-qubit computers. For example, it would be useful to have a 1024 qubit machine to simultaneously represent all 1024 bit states. Quantum error correction might solve the problem, but we are yet to see practical quantum computers.
  - amichail 17y ago
    Where does quantum cryptography fit into this? http://en.wikipedia.org/wiki/Quantum_cryptography http://en.wikipedia.org/wiki/Quantum_cryptography Does this have anything to do with quantum computing?
    - rdtsc 17y ago
      You are right, thank you. I embarrassingly forgot quantum cryptography.
      - amichail 17y ago
        But it seems that quantum cryptography allows you to do more than what is possible with classical computing: namely, to detect someone listening in on your communication. What is the relationship between quantum cryptography and quantum computing?
      - enki 17y ago
        you were right to leave it out - quantum cryptography and quantum computing have only the quantum in common. (i've published on quantum cryptography protocols)
- est 17y ago
  sleep(3) will be exact natural time three seconds, and you can't hack the system clock like SpeedGear to speed it up or slow it down on a quantum computer. And this leads to some encryption applications.
chrjozefharibo 17y ago
A grid of coupled qubits can be used to simulate quantum systems. A quantum system many physicists like to simulate is the Hubbard model (http://en.wikipedia.org/wiki/Hubbard_model http://en.wikipedia.org/wiki/Hubbard_model) . A simulation of the Hubbard model can possibly lead to a better understanding of high temperature superconductivity. This in turn can tell physicists where to look for room-temperature superconductors, the discovery of which will drastically transform the world as we know it. This is in my opinion the most important application of a quantum computer.
Keyframe 17y ago
Quantum Computing seems like voodoo to me, I have to read up more about it. Anyone care enough to explain a bit to me how data compression can benefit from it?
cool-RR 17y ago
Waiting for Scott Aaronson, http://scottaaronson.com/blog/ http://scottaaronson.com/blog/ , to give his verdict.

53 points by TravisLS 17y ago

I'm curious, what kinds of application ideas exist that are possible on quantum computers that aren't on regular computers?

amichail 17y ago
Factoring is possible in polynomial time.
- dave_au 17y ago
  From what I can remember, Schors algorithm gives you a polynomial speedup for factoring rather than putting it in polynomial time. It's been a little while since I was up to speed on this though.
- lionheart 17y ago
  See, I've heard this before. But it really doesn't mean anything to most people. The only concrete example I can think of is cracking modern encryption. Does anybody have any ideas that would be useful to everyday life? I'm 100% sure that there are a ton.
  - deleted 17y ago
    [deleted]
  - rdtsc 17y ago
    Well unless users work for NSA, are somehow aware of encryption algorithms, are concerned about protecting their data, or are interested in factoring large numbers, this would not interest them much. Grover's search algorithm however, will speedup searching. It would be possible to search very large databases in a much shorter time : O(sqrt(n)) instead of O(n). Of course, many problems are based on searching so it is hard to enumerate all the possible end-user visible effects of this.
    - fauigerzigerk 17y ago
      What about the data that is searched? Where would it be stored for a quantum computer to access it without losing all the speedup on IO?
      - rdtsc 17y ago
        Idealy only an index would be searched. For example when a sorting algorithm is presented, typically we assume that items are just integers. So if the database itself is huge, one would take a column and feed that into the quantum computer along with a matching function and a search item and the output would be the position of the item in the column. In general it is assumed that 'items' are integers. That is general enough. But since no practical implementations exist, still we still don't know how it would work in the real world with a real database. Here is a more in depth (and somewhat dramatic) explanation: For N, items to be search, it would take log2(N) qubits (that's enough to represent all N states). The matching function would have to be a quantum gate/operator. In other words, matching is performed in the quantum world. The idea behind quantum algorithms is to encode the input in a set of qubits, then make them interact in a way that creates a superposition of states. A superposition of states can be thought of as sending the input into a 'magic' quantum world, where N qubits simoultaneously represent all 2^N binary states. Then a set of quantum operators (gates) are applied to the state vector, while it is still in this magic quantum world. All is fine and dandy (provided that we can mentain the whole quantum world in a stable/isolated state). Then the 'sad' part is that once we measure the result and bring it into the 'real' world, the whole 'magic' quantum world collapses on itself, and only one particular state out of 2^N emerges. The trick is then to apply the quantum operators such that the probability of the quantum world collapsing to one particular 2^N state is increased. In case of Grover's algorithm that is what happens. The quantum operators increase the probability of the quantum state collapsing to the matched index. It is a probabilistic algorithm in the sense that it might have to be run a couple of times. EDIT: removed stupid spelling errors
  - korch 17y ago
    You can use polynomial time factoring to prove P = NP. Which means you have simultaneously solved a ton of outstanding optimization problems in science and engineering, and would allow for the creation of AI, clean renewable energy and practical space travel. Obviously those innovations would lead to the biggest change in the history of human civilization, and probably would cause lasting world peace. All from something as "useless" as factoring integers. True story.
nearestneighbor 17y ago
If time is not a constraining factor, then none (Turing-completeness). Applications requiring much parallelism, like NP-complete problems, may be more amenable to being solved by quantum computers in the future.
RiderOfGiraffes 17y ago
Breaking RSA, and most (all?) current forms of crypto used on the 'net.
JulianMorrison 17y ago
These are uses I recall from a recent lecture on QC: Using "adiabatic" qbits (not like this one), it seems you can solve any problem that can be structured as a low energy state. Examples of these are: PCB track routing, city planning, some kinds of pattern matching search in large datasets such as gene maps. There are possible applications to AI because it can efficiently update a neural network or a Bayes net. Also (not sure what kind of qbits are best for this) you should be able to simulate a quantum-influenced process, such as protein folding, one for one rather than via exhaustive calculation on supercomputers. Factoring crypto is often cited, but to be honest it's a very boring application compared to the many others.
rdtsc 17y ago
Theoretically none. Quantum computers are universal Turing machines. The main advantage of quantum computers is speedup. 5 years ago (when I took a couple of courses in QC) there were basically 2 quantum algorithms -- Shor's factorization and Grover's search. The former speeds up integer factorization (and discrete logarithm) and brings it to polynomial time, and the later speeds up search from O(n) to O(sqrt(n)). So just being able to quickly factor integers breaks a lot of encryption algorithms, and a faster search would really help with data processing. One of the main difficulty with quantum computers is quantum de-coherence. Qubits when they are entangled must be isolated from the outside environment until the final result measurement is taken. That is what is preventing the creation of large, multi-qubit computers. For example, it would be useful to have a 1024 qubit machine to simultaneously represent all 1024 bit states. Quantum error correction might solve the problem, but we are yet to see practical quantum computers.
- amichail 17y ago
  Where does quantum cryptography fit into this? http://en.wikipedia.org/wiki/Quantum_cryptography http://en.wikipedia.org/wiki/Quantum_cryptography Does this have anything to do with quantum computing?
  - rdtsc 17y ago
    You are right, thank you. I embarrassingly forgot quantum cryptography.
    - amichail 17y ago
      But it seems that quantum cryptography allows you to do more than what is possible with classical computing: namely, to detect someone listening in on your communication. What is the relationship between quantum cryptography and quantum computing?
    - enki 17y ago
      you were right to leave it out - quantum cryptography and quantum computing have only the quantum in common. (i've published on quantum cryptography protocols)
est 17y ago
sleep(3) will be exact natural time three seconds, and you can't hack the system clock like SpeedGear to speed it up or slow it down on a quantum computer. And this leads to some encryption applications.

chrjozefharibo 17y ago

A grid of coupled qubits can be used to simulate quantum systems. A quantum system many physicists like to simulate is the Hubbard model (http://en.wikipedia.org/wiki/Hubbard_model http://en.wikipedia.org/wiki/Hubbard_model) . A simulation of the Hubbard model can possibly lead to a better understanding of high temperature superconductivity. This in turn can tell physicists where to look for room-temperature superconductors, the discovery of which will drastically transform the world as we know it. This is in my opinion the most important application of a quantum computer.

Keyframe 17y ago

Quantum Computing seems like voodoo to me, I have to read up more about it. Anyone care enough to explain a bit to me how data compression can benefit from it?

cool-RR 17y ago

Waiting for Scott Aaronson, http://scottaaronson.com/blog/ http://scottaaronson.com/blog/ , to give his verdict.