Abstract
We study a variant of quantum circuit complexity, the binding complexity: Consider an -qubit system divided into two sets of qubits each () 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, straddling gates always suffice. We then prove any unitary synthesis can be accomplished with straddling gates. Furthermore, we extend our results to multipartite systems, and show that any -partite Schmidt decomposable state has binding complexity linear in , 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.
- Received 14 October 2021
- Accepted 3 June 2022
DOI:https://doi.org/10.1103/PhysRevA.105.062430
©2022 American Physical Society