What is your opinion and thoughts about possible ways to get an answer whether problems that are solvable on quantum computer within polynomial time (BQP) can be solved withing polynomial time on hypothetical machine that has discrete ontology? The latter means that it doesn't use continuous manifolds and such. It only uses discrete entities and maybe rational numbers as in discrete probability theory?

  • We could certainly make up hypothetical, but impossible-to-build, machines with discrete ontology that are more powerful than quantum computers. But I don't think this is what you're trying to ask. Please clarify. – Peter Shor Oct 8 at 19:55
  • @PeterShor Now I'm curious how that is possible to make up such machines that are more powerful than quantum computers so they do not utilize oracles of some kind. Is it really possible? Some people on math subreddits say that it's possible to make up a machine with countable infinite ontology (that I asked about in the OP) right from quantum computer: reddit.com/r/math/comments/9m2ic0 – Peter Zagubisalo Oct 9 at 7:26
  • @PeterShor The BQP class is derived from Quantum Mechanics that is a reality abstraction. I assumed the workings of the universe are compactly encoded in the quantum computers architecture. When I asked the OP question I had two questions in mind: 1) are discrete and countable-infinite ontologies of the Universe still possible or they were ruled out? 2) what is the minimal math model of a computing machine that is as powerful as quantum computer? I was going to later think/ask about such a model if I got enough evidence that discrete and countable-infinite machine as powerful as QC is possible – Peter Zagubisalo Oct 9 at 7:28
  • @PeterShor For one project of mine I need to have a really compact abstraction of universe workings regarding computations that take into account state of art physics. Discrete BQP class machine was my best idea to get one. – Peter Zagubisalo Oct 9 at 7:31
  • @PeterShor By the way: may be you know if there is an oracle that can be added to ~turing machine so that it would be BQP fast? – Peter Zagubisalo Oct 9 at 8:02

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.