Straddling-gates problem in multipartite quantum systems

Abstract

We study a variant of quantum circuit complexity, the binding complexity: Consider a $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? Firstly, our work suggests that, without making assumptions on the entanglement spectrum, $\Theta (2^{k_1})$ straddling gates always suffice. We then prove any $\text{U}(2^n)$ unitary synthesis can be accomplished with $\Theta (4^{k_1})$ 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 multi-separable 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.

6 pages, 2 figures

References in corpus (5)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Synthesis of Quantum Logic Circuits
• Efficient Distributed Quantum Computing
• How many CNOT gates does it take to generate a three-qubit state ?
• Holographic simulation of correlated electrons on a trapped ion quantum processor

Cited by in corpus (3)

• The Complexity of Being Entangled
• Sequential quantum simulation of spin chains with a single circuit QED device
• Chern-Simons Type Characteristic Classes of Abelian Lattice Gauge Theory