3
$\begingroup$

In some papers such as this one the "space time volume" of an algorithm implementation is provided. However I am struggling to find a precise definition of that.

How is such quantity defined ?

$\endgroup$

1 Answer 1

2
$\begingroup$

Spacetime volume is the number of qubits used multiplied by the amount of time they are used. The classical analogue of this concept is CPU hours (how many CPUs for how many hours).

For example:

  • A ripple carry adder has $O(n)$ gates and $O(n)$ qubits, and takes $O(n)$ depth to run. Its spacetime volume is its qubits times its depth which is $O(n^2)$.
  • A carry lookahead adder also has $O(n)$ gates and $O(n)$ qubits, but it takes $O(\lg n)$ depth, so its spacetime volume is $O(n \lg n)$.
  • It's an open question whether there is a quantum adder with $O(n)$ spacetime volume. Classically, the carry save adder covers $O(n)$ bits and takes $O(1)$ depth but it uses irreversible steps. Quantumly the best I know is $O(n \lg(\lg(1/\epsilon)))$ where $\epsilon$ is a maximum error rate per operation based on using oblivious carry runways. Typically you need $\epsilon = 1/n^{O(1)}$ so this is roughly like saying $O(n \lg(\lg(n)))$.

Spacetime volume is a particularly important metric in surface code computations, because the computations are built topologically. They are built in a way that doesn't strongly distinguish between space and time. You can take a computation that progresses forward through time, "turn it on its side" in spacetime, and now you have a computation that progresses forward through space. This makes it a bit meaningless to improve the space or to improve the time, because you tend to be able to turn one into the other (up to hard constraints like non-Clifford feedback having to go forward in time, and needing enough space to hold the problem state). We can easily adjust the speed of a computation up or down by an order of magnitude by using reaction limited computation and varying the number of magic state factories running at the same time (using significant space). So we focus on spacetime volume.

Another reason to focus on volume is that a common mistake researchers make (including past me) is to only care about the duration of a computation or the space requirements of a computation. The result is ridiculous constructions that finish quickly but require quintillions of qubits, or save 3 qubits out of a thousand while making the computation take a hundred times longer. Focusing on volume helps avoid that particular failure mechanism.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.