Straddling-gates problem in multipartite quantum systems

We study a variant of quantum circuit complexity, the binding complexity: Consider an $n$-qubit system divided into two sets of $k_1, k_2$ qubits each ($k_1\le k_2$) and gates within each set are free; what is the least cost of two-qubit gates “straddling” the sets for preparing an arbitrary quantum state, assuming no ancilla qubits allowed? First, our work suggests that, without making assumptions on the entanglement spectrum, $\mathrm{\Theta }\left(2^{k_1}\right)$ straddling gates always suffice. We then prove any $\text{U}\left(2^n\right)$ unitary synthesis can be accomplished with $\mathrm{\Theta }\left(4^{k_1}\right)$ straddling gates. Furthermore, we extend our results to multipartite systems, and show that any $m$-partite Schmidt decomposable state has binding complexity linear in $m$, which hints its multiseparable property. This result not only resolves an open problem posed by Vijay Balasubramanian, who was initially motivated by the complexity = volume conjecture in quantum gravity, but also offers realistic applications in distributed quantum computation in the near future.

Figure 1

Disentangling a qubit. Top: For any input quantum state, one could disentangle any bit with two multiplexors; reversing this process gives an iterative algorithm for state preparation [11, 14]. Bottom: decomposing a $c$-control multiplexor with two $(c-1)$-control multiplexors and two cnot gates. In the diagram, the register with slash is an abbreviation for all control registers, white box denotes control bits and $R_k$ is a rotation gate along axis $k\in y,z$ with angles to be determined.

Figure 2

QSD process for an arbitrary unitary The diagram shows a recursive construction of a arbitrary unitary $U$, also know as the “quantum Shannon decomposition (QSD)” [16].