Straddling-gates problem in multipartite quantum systems

• URL: http://arxiv.org/abs/2110.06840v2
• Date: Thu, 23 Jun 2022 18:41:56 GMT
• Title: Straddling-gates problem in multipartite quantum systems
• Authors: Yuxuan Zhang
• Abstract summary: We study a variant of quantum circuit complexity, the binding complexity. We show that any $m$partite Schmidt decomposable state has binding complexity linear in $m$, which hints its multi-separable property.
• Score: 20.428960719376164
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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\leq 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.

Related papers

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Systematic construction of topological-nontopological hybrid universal quantum gates based on many-body Majorana fermion interactions [0.0]
  Topological quantum computation by way of braiding of Majorana fermions is not universal quantum computation. We make a systematic construction of the C$n$Z gate, C$n$NOT gate and the C$n$SWAP gate.
  arXiv  Detail & Related papers  (2023-04-13T04:41:29Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Does qubit connectivity impact quantum circuit complexity? [5.908927557774895]
  Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. In this paper, we show that all $n$-qubit unitary operations can be implemented by quantum circuits of $O(4n)$ depth and $O(4n)$ size.
  arXiv  Detail & Related papers  (2022-11-10T08:38:29Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
  Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states. We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
  arXiv  Detail & Related papers  (2022-02-23T04:19:57Z)
• Halving the cost of quantum multiplexed rotations [0.0]
  We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls. Our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations.
  arXiv  Detail & Related papers  (2021-10-26T06:49:44Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.