3 ms·

Quantum doesn’t help for NP problems. In the case of codebreaking, where QC may have an advantage, AI is unlikely to provide an alternative because modern AI i

Quantum doesn’t help for NP problems. In the case of codebreaking, where QC may have an advantage, AI is unlikely to provide an alternative because modern AI is all based on finding probabilistic patterns and cryptography is explicitly designed to be resistant to that kind of attack.

firtoz 3y ago
Can you please elaborate?
- canjobear 3y ago
  The class of this problems where quantum computing gives an advantage is called BQP and it includes things like factoring but it is not known to include NP complete problems like the traveling salesman.
  - firtoz 3y ago
    Thank you!
wegfawefgawefg 3y ago
I have not programmed a quantum computer before. My current state of ignorance, and so im relying only on intuition here, is that it is massively parralel in the same way that the surface of water in your cup is massively parralel. To program a serial algorithm in a quantum computer would be to miss the point. You could encode the interactions between clumps of qbits to function as nodes in a wave simulation. There would be few enough nodes in the wave that it would be not equivalent to a true wave simulation. It would be a discretization, but now it functions as an analog asic like proxy for the real thing. If the groups of qbits are smaller than the true nodes in a wave surface your computation would be faster than the real thing, but lower precision. In a classical computer this would have to be done with buffers, or a very narrow set of parralel deterministic programs, otherwise impossible. (examples: a subset of cellular automata rules, gravity sort) Is any of that right or am i completely off base.
- TachyonicBytes 3y ago
  One of the challenges of quantum computing is getting the useful results back into "classical" mode, where you can use them. Theoretically that's one of the hurdles of getting better theoretical performance than a classical computer. What you describe is more akin to how a GPU works, but in this case, you can't "just get" the result from the GPU.
- dragontamer 3y ago
  Quantum is not parallel. Quantum is quantum. We did a few quantum gate simulations in my college back in the day. The gist is that entangling bits (say b0, b1, b2, b3 are all entangled), has special properties. You can almost perform retroactive computing. you can send these values to quantum gates to define properties, like b0 + b1 = b2 * b3. Later, you unentangled the values and they will 'snap' into some true state. Like b0,b1,b2,b3 == 1111, but the values 0001 or 0010 are also possible. There is nothing 'parallel' about this. It's just a quantum operator using the properties of entanglement / disentanglement for the purposes of computation. ------- I'd say that quantum is closer to retroactive computing than parallel. Operations seemingly go backwards in time thanks to entanglement. That doesn't mean quantum is useful in all algorithms, but it seemingly has applications in cryptography and 3SAT / NP Complete and... Lol simulations of quantum effects. -------- Ultimately, Quantum is only useful if you get enough bits at a time entangled. For now, it's faster for standard computers to brute-force all 2^32 bit combinations rather than using lasers+diamonds to entangle 32-bits and perform the operations. Quantum needs more entanglement and at lower costs to become competitive. But maybe it happens. At very least, quantum computers do exist but who knows how long it will be before they are competitive.
daveed 3y ago
^ Just pointing out, the parent didn't say NP-hard or -complete, so they weren't wrong (but could be misunderstood). But saying Quantum doesn't help for NP isn't right either.
- canjobear 3y ago
  Fair enough!
marcosdumay 3y ago
> Quantum doesn’t help for NP problems. Notice that the GP is about the other way around. Solving NP-hard problems will absolutely make quantum computers useless. And in the case of physics simulation (the actually valuable use for a quantum computer), there's no guarantee that you can't find a probabilistic solution.

firtoz 3y ago

Can you please elaborate?

canjobear 3y ago
The class of this problems where quantum computing gives an advantage is called BQP and it includes things like factoring but it is not known to include NP complete problems like the traveling salesman.
- firtoz 3y ago
  Thank you!

wegfawefgawefg 3y ago

I have not programmed a quantum computer before. My current state of ignorance, and so im relying only on intuition here, is that it is massively parralel in the same way that the surface of water in your cup is massively parralel. To program a serial algorithm in a quantum computer would be to miss the point. You could encode the interactions between clumps of qbits to function as nodes in a wave simulation. There would be few enough nodes in the wave that it would be not equivalent to a true wave simulation. It would be a discretization, but now it functions as an analog asic like proxy for the real thing. If the groups of qbits are smaller than the true nodes in a wave surface your computation would be faster than the real thing, but lower precision. In a classical computer this would have to be done with buffers, or a very narrow set of parralel deterministic programs, otherwise impossible. (examples: a subset of cellular automata rules, gravity sort) Is any of that right or am i completely off base.

TachyonicBytes 3y ago
One of the challenges of quantum computing is getting the useful results back into "classical" mode, where you can use them. Theoretically that's one of the hurdles of getting better theoretical performance than a classical computer. What you describe is more akin to how a GPU works, but in this case, you can't "just get" the result from the GPU.
dragontamer 3y ago
Quantum is not parallel. Quantum is quantum. We did a few quantum gate simulations in my college back in the day. The gist is that entangling bits (say b0, b1, b2, b3 are all entangled), has special properties. You can almost perform retroactive computing. you can send these values to quantum gates to define properties, like b0 + b1 = b2 * b3. Later, you unentangled the values and they will 'snap' into some true state. Like b0,b1,b2,b3 == 1111, but the values 0001 or 0010 are also possible. There is nothing 'parallel' about this. It's just a quantum operator using the properties of entanglement / disentanglement for the purposes of computation. ------- I'd say that quantum is closer to retroactive computing than parallel. Operations seemingly go backwards in time thanks to entanglement. That doesn't mean quantum is useful in all algorithms, but it seemingly has applications in cryptography and 3SAT / NP Complete and... Lol simulations of quantum effects. -------- Ultimately, Quantum is only useful if you get enough bits at a time entangled. For now, it's faster for standard computers to brute-force all 2^32 bit combinations rather than using lasers+diamonds to entangle 32-bits and perform the operations. Quantum needs more entanglement and at lower costs to become competitive. But maybe it happens. At very least, quantum computers do exist but who knows how long it will be before they are competitive.

daveed 3y ago

^ Just pointing out, the parent didn't say NP-hard or -complete, so they weren't wrong (but could be misunderstood). But saying Quantum doesn't help for NP isn't right either.

canjobear 3y ago
Fair enough!

marcosdumay 3y ago

> Quantum doesn’t help for NP problems. Notice that the GP is about the other way around. Solving NP-hard problems will absolutely make quantum computers useless. And in the case of physics simulation (the actually valuable use for a quantum computer), there's no guarantee that you can't find a probabilistic solution.