Class Description

BQTIME(f(n)): Bounded-Error Quantum f(n)-Time

Same as BQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [BV97].

Linked From

PhP: Physical Polynomial-Time

Defined by Valiant [Val03] to be "the class of physically constructible polynomial resource computers" (characterizing what "can be computed in the physical world in practice"). There he says that PhP contains P and BPP, but that it is open whether PhP contains BQP, since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.

For what it's worth, the present zookeeper has more qualms about admitting DTIME(n1000) into PhP than BQTIME(n2). It is very possible that the total number of bits or bit tranisitions that can be witnessed by any one observer in the universe is finite. (Recent observations of the cosmological constant combined with plausible fundamental physics yields a bound of 10k with k in the low hundreds.) In practice, less than 1050 bits and less than 1080 bit transitions are available for human use. (This is combining the number of atoms in the Earth with the number of signals that they can exchange in a millenium.)

The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether BQP is a realistic class.

More about...