5 ms·

I think almost everyone in the field would reject your third claim. There is a great deal of work being done on applying the speedup afforded by quantum mechani

I think almost everyone in the field would reject your third claim. There is a great deal of work being done on applying the speedup afforded by quantum mechanics to classically hard problems. The current consensus (at least among people I speak to) is that a quantum computer will probably be able to solve some problems which are in NP (and not in P), but will probably not be able to solve an NP-hard problem. Your intuitive view is appealing, but I don't think one should get too hung up on intuition. Our intuition was honed for millions of years to avoid large wild animals and avoid falling out of trees in prehistoric Africa. It generally sucks pretty badly at making guesses about the fundamental nature of the universe (or at least mine does). Edit: by the way a faster than light communication "ansible" is functionally equivalent to a machine that sends messages back in time. I disagree with your view that such a machine is more plausible than the view that some ftl stuff happens on the "backend" but is hidden from the "frontend". Having said that my view is that there is no ftl stuff on the back or front end, this is consistent with something like the many worlds interpretation of quantum mechanics, which is entirely local and causal (no ftl stuff).

FeepingCreature 6y ago
I'm aware and agree that quantum computer speed is very probably greater than classical and may allow some NP. My point is more that I'd expect the performance cost of QM to equal the complexity class of QM. I don't know, is that the case in current research? Whenever people talk about how expensive it is to compute QM, that always sounds a lot higher than the actual performance they get back out. Or maybe I just have a bad imagination for how high NP really is. Disagreeing again with the "Ansible is unrealistic" view: I agree it's unrealistic in a global sense, I just think all of its unrealism comes from the use of FTL in the backend. FTL + relativity produces timetravel, yes. I just think it's implausible to expect a physical universe to first provision the mechanics for FTL, then provision a system that gives you timetravel when exposed to FTL, and then very carefully separate those two systems so that they computationally never touch, even though in theory they could! and so in a sense, this physical theory implies that this universe has to be prepared, in principle, to allow time travel and account for it, and having gained this capability has elected to specifically not use it. It just stinks of a massive Occam violation - the potential for time travel is an "entity without necessity", and the theory is bloated by it twice over; once by its inclusion in the physical logic and once again by the additional exclusion mechanism that makes it unusable in every reachable state. And so the ansible universe pays slightly less cost just by leaving out the global censor. Am I saying "no correct theory can look like this"? No! I am saying it enters the race with a huge handicap.
- simiones 6y ago
  > My point is more that I'd expect the performance cost of QM to equal the complexity class of QM. My understanding is that that is a yes - with a quantum computer, quantum simulations [are expected to] run in linear time instead of the current exponential time.
  - eigenket 6y ago
    I think this is not correct. A fundamental problem in quantum simulation of quantum systems is the Hamiltonian problem, where you give me a Hamiltonian H, which is the sum of polynomially many little local Hamiltonians H_i each of which acts on at most k subsystems of your big total system. Then you give me two numbers a and b (with some technical constraints) and ask me whether the ground state energy of H is between a and b. This problem is QMA-complete as long as k >= 2, and known to be QMA-hard even for some pretty nice looking Hamiltonians. Here QMA stands for Quantum Merlin-Arthur which is the complexity class equivalent to MA (Merlin-Arthur) for classical computers. You can think of MA as being related to BPP in the same way that NP is related to P, and this is the same way that QMA is related to BQP. Basically QMA problems are not expected to be solved efficiently by a quantum computer.
    - simiones 6y ago
      I am way out of my depth here, thank you for weighing in!

FeepingCreature 6y ago

I'm aware and agree that quantum computer speed is very probably greater than classical and may allow some NP. My point is more that I'd expect the performance cost of QM to equal the complexity class of QM. I don't know, is that the case in current research? Whenever people talk about how expensive it is to compute QM, that always sounds a lot higher than the actual performance they get back out. Or maybe I just have a bad imagination for how high NP really is. Disagreeing again with the "Ansible is unrealistic" view: I agree it's unrealistic in a global sense, I just think all of its unrealism comes from the use of FTL in the backend. FTL + relativity produces timetravel, yes. I just think it's implausible to expect a physical universe to first provision the mechanics for FTL, then provision a system that gives you timetravel when exposed to FTL, and then very carefully separate those two systems so that they computationally never touch, even though in theory they could! and so in a sense, this physical theory implies that this universe has to be prepared, in principle, to allow time travel and account for it, and having gained this capability has elected to specifically not use it. It just stinks of a massive Occam violation - the potential for time travel is an "entity without necessity", and the theory is bloated by it twice over; once by its inclusion in the physical logic and once again by the additional exclusion mechanism that makes it unusable in every reachable state. And so the ansible universe pays slightly less cost just by leaving out the global censor. Am I saying "no correct theory can look like this"? No! I am saying it enters the race with a huge handicap.

simiones 6y ago
> My point is more that I'd expect the performance cost of QM to equal the complexity class of QM. My understanding is that that is a yes - with a quantum computer, quantum simulations [are expected to] run in linear time instead of the current exponential time.
- eigenket 6y ago
  I think this is not correct. A fundamental problem in quantum simulation of quantum systems is the Hamiltonian problem, where you give me a Hamiltonian H, which is the sum of polynomially many little local Hamiltonians H_i each of which acts on at most k subsystems of your big total system. Then you give me two numbers a and b (with some technical constraints) and ask me whether the ground state energy of H is between a and b. This problem is QMA-complete as long as k >= 2, and known to be QMA-hard even for some pretty nice looking Hamiltonians. Here QMA stands for Quantum Merlin-Arthur which is the complexity class equivalent to MA (Merlin-Arthur) for classical computers. You can think of MA as being related to BPP in the same way that NP is related to P, and this is the same way that QMA is related to BQP. Basically QMA problems are not expected to be solved efficiently by a quantum computer.
  - simiones 6y ago
    I am way out of my depth here, thank you for weighing in!