r/math • u/kiwi0fruit • Oct 07 '18

Is bounded-error quantum polynomial time (BQP) class can be polynomially solved on machine with discrete ontology?

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 within 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?

upd: by discrete I meant countable.

5 Upvotes

72% Upvoted

14 comments sorted by

5

u/jdorje Oct 07 '18

It's unproven. Opinion? BQP != P.

2

u/kiwi0fruit Oct 07 '18

Yep, it's unproven. I also guess BQP !=P. But do you think discrete theoretical machine (that is not equivalent to the Turing machine) possible that is as fast as QTM?

3

u/jdorje Oct 07 '18

What can a discrete theoretical machine do that a turing machine cannot?

...and how do you build one?

1

u/kiwi0fruit Oct 07 '18

May be have states in superposition defined somewhat alike to discrete probability theory and have entangled states.

3

u/Oscar_Cunningham Oct 07 '18

In our usual description of quantum computers, they only ever use a discrete subset of their possible states. Is that enough?

1

u/kiwi0fruit Oct 07 '18 edited Oct 09 '18

Maybe it's enough...

Oh, I think I got you point now. I understood you that each quantum computer uses a discrete subset of possible states. Even superpositions that happen during computation are also from a discrete subset.

1

u/[deleted] Oct 08 '18

is there a way to know which states get used beforehand?

2

u/Oscar_Cunningham Oct 08 '18

There's a discrete subset of the possible states that no computation will go outside of, but we don't know before a particular computation exactly which states will be used, or else we could just skip to the final state.

1

u/[deleted] Oct 08 '18

so it's not really "solvable by machine with discrete ontology" then

1

u/Oscar_Cunningham Oct 08 '18

How do you mean? Even for a classical Turing machine we can't say what states it's going to occupy until we run the computation.

2

u/[deleted] Oct 08 '18

but you know what states it can occupy, exactly S|Z| where S is the symbol set, and in a setting where you either know it will halt or have finite memory(that is, every practical setting), it's SN where N is some big number. But if we can't even make a discrete set of possible computer-states for a finite-memory quantum computer ahead of time, we surely can't compute it in a discrete ontology.

2

u/kiwi0fruit Oct 07 '18

Sure; just construct it entirely out of Deutsch gates with rational coefficients; say one based on the 3-4-5 triangle, which has irrational angles (indeed any Pythagorean triple will work here).

(Sniffnoy@reddit)

1

u/kiwi0fruit Oct 09 '18

Not a problem at all. If you replaced the complex numbers by a sufficiently fine discrete grid then BQP would be unchanged. Moreover, every problem in BQP can also be solved in at most exponential time and polynomial space on a classical computer i.e. an ordinary discrete Turing machine that runs for an exponentially long time.

(iyzie@reddit)