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.

arXiv comment6 pages, 2 figures

References in corpus (25)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Elementary gates for quantum computation
• Three qubits can be entangled in two inequivalent ways
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Quantifying Entanglement
• Trapped-Ion Quantum Computing: Progress and Challenges
• Synthesis of Quantum Logic Circuits
• Demonstration of the trapped-ion quantum-CCD computer architecture
• Characterizing Entanglement
• A Schmidt number for density matrices
• Quantum Circuits for General Multiqubit Gates
• Quantum-assisted quantum compiling
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Perspectives on quantum transduction
• Multi-particle entanglement and its applications to cryptography
• Efficient Distributed Quantum Computing
• On Multipartite Pure-State Entanglement
• Holographic quantum algorithms for simulating correlated spin systems
• Copenhagen vs Everett, Teleportation, and ER=EPR
• Fault-Tolerant Operation of a Quantum Error-Correction Code
• Monogamy, polygamy, and other properties of entanglement of purification
• Binding Complexity and Multiparty Entanglement
• 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