Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve (2018)

Re:Finally, a Problem That Only Quantum Computers Will Ever ... by uwu123 on Sunday November 08, 2020 @05:23PM (#25029679)

So, all the buzzwords aside, I thought that you can simulate quantum computers on a Turing machine. Consequently, computers and quantum computers should be able to solve exactly the same class of problems.

[ Parent | on HN ]

Re:Finally, a Problem That Only Quantum Computers Will Ever ... by eunice-aiden on Tuesday November 17, 2020 @11:01AM (#25125289)

They're equivalent from a computability perspective, not a complexity perspective. We don't really know whether Turing machines are capable of simulating quantum Turing machines efficiently. In fact, it's conjectured not to be the case.

[ Parent | on HN ]