Kosuke Matsui

Scaling up the number of qubits available on quantum processors remains technically demanding; it is therefore crucial to clarify the number of qubits required to execute a quantum computation. When circuit compilation techniques such as mid-circuit measurements and delayed input preparation are permitted, the qubit requirement of a given quantum computation can be smaller than that implied by its naive description. However, no general method has been known for characterizing how much such reductions can be achieved. In this work, we characterize lower and upper bounds on the number of qubits required to implement a given quantum computation in terms of the causal structure of the corresponding quantum instrument. We further show that these lower and upper bounds coincide for quantum computations used in entanglement distillation protocols, and thereby obtain optimal space requirements for several well-known entanglement distillation protocols.