Is BQP only about time? Is this meaningful?

Question

The complexity class BQP (bounded-error quantum polynomial time) seems to be defined only considering the time factor. Is this always meaningful? Do algorithms exist where computational time scales polynomially with the input size but other resources such as memory scale exponentially?

Answer 1

BQP is defined considering circuit size, which is to say the total number of gates. This means that it incorporates:

• Number of qubits — because we can ignore any qubits which are not acted on by a gate. This will be polynomially bounded relative to the input size, and often a modest polynomial (e.g. Shor's algorithm only involves a number of qubits which is a constant factor times the input size).
• Circuit depth (or 'time') — because the longest the computation could take is if we perform one gate after another, without performing any operations in parallel.
• Communication with control systems — because the gates being performed are taken from some finite gate set, and even if we allow intermediate measurements, the amount of communication required to indicate the result of the measurement and the amount of computation required to determine what is done next is usually a constant for each operation.
• Interactions between quantum systems — even if we consider an architecture which does not have all-to-all interactions or anything close to it, we can simulate having that connectivity by performing explicit SWAP operations, which can themselves be decomposed into a constant number of two-qubit operations. This might give us a noticeable polynomial overhead which impacts how practical an algorithm is for a given architecture, but it does not hide an exponential amount of work.
• Energy — again because the circuits are decomposed into a finite gate-set, there is no obvious way to obtain an apparent speed-up by "doing the gates faster" or by hiding work in an exotic interaction, if our bound is in terms of the number of operations performed from a fairly basic set of operations. This consideration is more important in adiabatic quantum computing: we can't try to avoid small gaps just by amplifying the entire energy landscape as much as we like — meaning that we must take longer to do the computation instead, corresponding in the circuit picture to a circuit with more gates.

In effect, counting the number of gates from a constant-sized set captures many things which you might worry about as practical resources: it leaves very little space to hide anything which is secretly very expensive.

Answer 2

Not for memory, at least, as every memory access requires $O(1)$ 'time'.

In the term time complexity, 'time' is a bit misleading, as we actually count the number of elementary operations required to perform an algorithm. Under the additional assumption that these operations can be performed in '$O(1)$ time', we can say that our algorithm has a 'time complexity'. But what we are actually mean is that we have a 'operation complexity' which we express in time.

I think it is clearer that counting elementary operations is a fundamental and important measure of the number of resources required by an algorithm, as we can always decide how many resources each elementary operation requires.

While in the definition of BQP and for quantum algorithms we consider circuit complexity instead of 'operation complexity', circuit complexity can again defined in terms of operations on Turing machines, so the same reasoning applies.