# How is the "space time volume" defined?

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 ?

• 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)))$$.