Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2203.10106

Non-local computation of quantum circuits with small light cones

Kfir Dolev, Sam Cree

Published Mar 18, 2022• 17 citations
arXivHTMLPDF

Abstract

The task of non-local quantum computation requires implementation of a unitary on $n$ qubits between two parties with only one round of communication, ideally with minimal pre-shared entanglement. We introduce a new protocol that makes use of the fact that port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. Whereas previous protocols have entanglement cost independent of the unitary or scaling with its complexity, the cost of the new protocol scales with the non-locality of the unitary. Specifically, it takes the form $\sim n^{4V}$ with $V$ the maximum volume of a past light cone in a circuit implementing the unitary. Thus we can implement unitary circuits with $V\sim O(1)$ using polynomial entanglement, and those with $V\sim \mathrm{polylog}(n)$ using quasi-polynomial entanglement. For a general unitary circuit with $d$ layers of $k$-qubit gates $V$ is at most $k^d$, but if geometric locality is imposed it is at most polynomial in $d$. We give an explicit class of unitaries for which our protocol's entanglement cost scales better than any known protocol. We also show that several extensions can be made without significantly affecting the entanglement cost - arbitrary local pre- and post-processing; global Clifford pre- and post-processing; and the addition of a polynomial number of auxiliary systems.

DOI
10.48550/arxiv.2203.10106

Related papers

Equivalence of non-local computation tasks beyond Clifford operations

Andreas Bluhm, Simon Höfer, Alex May +2 more

Non-local quantum computation (NLQC) studies how two collaborating players can implement channels on distributed systems using a single simultaneous round of quantum communication and shared entanglement. NLQC has applications in diverse areas, ranging from quantum position-verification to quantum gravity. Recently, it has been realized that the relationships among families of NLQC tasks are highly structured: many seemingly distinct tasks are related by reductions, wherein implementations of one task can be used to efficiently implement a second task. This is analogous to the notion of reduction in complexity theory, and reveals the relative hardness of NLQC tasks. In this work we continue the study of reductions among NLQC tasks. We focus on NLQC examples of the greatest interest in quantum position-verification; in particular examples involving large classical inputs and fixed-size quantum inputs, since these constitute the most feasible protocols for position-verification schemes. Within this setting, we find many new relationships among NLQC tasks. For instance, protocols for the simplest example of redirecting a quantum system based on a classical control imply protocols for controlled single qubit measurements in arbitrary bases, the controlled application of any Clifford unitary, and even the controlled application of any unitary of the form $U=C_1DC_0$ with $D$ an arbitrary diagonal unitary and $C_0, C_1$ Clifford circuits. This implies that many feasible position-verification schemes have the same asymptotic scaling for their entanglement cost, and hence a similar level of security. Our techniques rely on ideas from gate teleportation and measurement based quantum computation, among other areas, bringing several new strategies into NLQC which may be of independent interest.

quant-pharXiv:2606.26354•Jun 26, 2026•3 citations

Bounds on Instantaneous Nonlocal Quantum Computation

Alvin Gonzales, Eric Chitambar

Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-qubit gate can be implemented by LOBC with ϵ-error using O(log(1/ϵ)) entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as O(1/ϵ). We also consider the family of binary controlled gates on dimensions dA⊗ dB. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of log dB ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when dA= 2. This demonstrates an unbounded gap between the entanglement costs of LOCC and LOBC gate implementation. Whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.

arXiv:1810.00994•IEEE Transactions on Information Theory•Oct 29, 2019•24 citations

A complexity theory for non-local quantum computation

Andreas Blühm, Simon Höfer, Alex May +3 more

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f -measure and f -route, the two best studied NLQC tasks, are in fact equivalent under O ( 1 ) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f -measure. For instance, we obtain sub-exponential upper bounds on f -measure for all functions, and efficient protocols for functions in the complexity class M o d k L . Beyond this, we study a number of other examples of NLQC tasks and their relationships.

arXiv:2505.23893•Quantum•Jul 1, 2026•11 citations

Entanglement-efficient bipartite-distributed quantum computing

Jun-Yi Wu, Kosuke Matsui, Tim Forrer +5 more

In noisy intermediate-scale quantum computing, the limited scalability of a single quantum processing unit (QPU) can be extended through distributed quantum computing (DQC), in which one can implement global operations over two QPUs by entanglement-assisted local operations and classical communication. To facilitate this type of DQC in experiments, we need an entanglement-efficient protocol. To this end, we extend the protocol in [Eisert et. al., PRA, 62:052317(2000)] implementing each nonlocal controlled-unitary gate locally with one maximally entangled pair to a packing protocol, which can pack multiple nonlocal controlled-unitary gates locally using one maximally entangled pair. In particular, two types of packing processes are introduced as the building blocks, namely the distributing processes and embedding processes. Each distributing process distributes corresponding gates locally with one entangled pair. The efficiency of entanglement is then enhanced by embedding processes, which merge two non-sequential distributing processes and hence save the entanglement cost. We show that the structure of distributability and embeddability of a quantum circuit can be fully represented by the corresponding packing graphs and conflict graphs. Based on these graphs, we derive heuristic algorithms for finding an entanglement-efficient packing of distributing processes for a given quantum circuit to be implemented by two parties. These algorithms can determine the required number of local auxiliary qubits in the DQC. We apply these algorithms for bipartite DQC of unitary coupled-cluster circuits and find a significant reduction of entanglement cost through embeddings. This method can determine a constructive upper bound on the entanglement cost for the DQC of quantum circuits.

arXiv:2212.12688•Quantum•Dec 5, 2023•43 citations

Perfect non-local quantum computation is impossible

Marten Folkertsma, Dmitry Grinko, Gina Muuss +1 more

Non-local quantum computation (NLQC) asks two parties to apply a joint operation to their quantum inputs using an entangled resource state and one round of simultaneous quantum communication. NLQC has applications across quantum information, including attacks on quantum position verification, communication complexity, and quantum gravity. Every bipartite unitary has an approximate NLQC protocol with finite entanglement, and exact protocols are known for several structured families. However, it has remained open whether every fixed unitary admits an exact protocol with finite-dimensional resources. We show that, even for two qubits, Haar-almost every unitary does not admit such a protocol, even when the resource state and local operations are tailored to the target. The proof first shows that smooth deformations of an exact protocol can only change its target by local unitaries. For a fixed architecture, semialgebraic geometry limits the exact protocols to finitely many connected families, so each architecture reaches only finitely many local-unitary orbits. Taking the union over all architectures, the exactly implementable unitaries form countably many local-unitary orbits. We also show that some natural targets do not admit a protocol: the controlled phase $\mathrm{diag}(1,1,1,e^{iθ})$ has no exact protocol with finite-dimensional resources whenever $e^{iθ}$ is transcendental, for instance for $θ= 1$. Our results also apply to localizable quantum measurements, whose outcome is obtained from local measurements on inputs and a shared entangled resource state without communication. A rank-one projective measurement in a Haar-random basis is almost surely not localizable with a finite-dimensional resource state and finitely many local outcomes.

quant-pharXiv:2609.40228•Oct 1, 2026•0 citations

Computational complexity and simulability of non-Hermitian quantum dynamics

Brian Barch, Daniel A. Lidar

Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: If coherent nonunitary evolution with renormalization could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP ( U ) as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on O ( 1 ) qubits that is not proportional to a unitary, with the state renormalized after each use of U . We prove that this model is powerful enough to decide every language in PostBQP (equivalently PP ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate U , NHBQP ( U ) = PostBQP = PP . PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a compensating cost limiting its efficiency. Additionally, we study simulation complexity of restricted classes of nonunitary systems by purifying them to postselected unitary evolution in a form preserving system locality. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability Ω ( 2 − poly ( n ) ) . Thus, adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.

arXiv:2506.03435•Physical Review Research•Jun 24, 2026•6 citations
The task of non-local quantum computation requires implementation of a unitary on nnn qubits between two parties with only one round of communication, ideally with minimal pre-shared entanglement. We introduce a new protocol that makes use of the fact that port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. Whereas previous protocols have entanglement cost independent of the unitary or scaling with its complexity, the cost of the new protocol scales with the non-locality of the unitary. Specifically, it takes the form ∼n4V\sim n^{4V}∼n4V with VVV the maximum volume of a past light cone in a circuit implementing the unitary. Thus we can implement unitary circuits with V∼O(1)V\sim O(1)V∼O(1) using polynomial entanglement, and those with V∼polylog(n)V\sim \mathrm{polylog}(n)V∼polylog(n) using quasi-polynomial entanglement. For a general unitary circuit with ddd layers of kkk-qubit gates VVV is at most kdk^dkd, but if geometric locality is imposed it is at most polynomial in ddd. We give an explicit class of unitaries for which our protocol's entanglement cost scales better than any known protocol. We also show that several extensions can be made without significantly affecting the entanglement cost - arbitrary local pre- and post-processing; global Clifford pre- and post-processing; and the addition of a polynomial number of auxiliary systems.
Non-local quantum computation (NLQC) studies how two collaborating players can implement channels on distributed systems using a single simultaneous round of quantum communication and shared entanglement. NLQC has applications in diverse areas, ranging from quantum position-verification to quantum gravity. Recently, it has been realized that the relationships among families of NLQC tasks are highly structured: many seemingly distinct tasks are related by reductions, wherein implementations of one task can be used to efficiently implement a second task. This is analogous to the notion of reduction in complexity theory, and reveals the relative hardness of NLQC tasks. In this work we continue the study of reductions among NLQC tasks. We focus on NLQC examples of the greatest interest in quantum position-verification; in particular examples involving large classical inputs and fixed-size quantum inputs, since these constitute the most feasible protocols for position-verification schemes. Within this setting, we find many new relationships among NLQC tasks. For instance, protocols for the simplest example of redirecting a quantum system based on a classical control imply protocols for controlled single qubit measurements in arbitrary bases, the controlled application of any Clifford unitary, and even the controlled application of any unitary of the form U=C1DC0U=C_1DC_0U=C1​DC0​ with DDD an arbitrary diagonal unitary and C0,C1C_0, C_1C0​,C1​ Clifford circuits. This implies that many feasible position-verification schemes have the same asymptotic scaling for their entanglement cost, and hence a similar level of security. Our techniques rely on ideas from gate teleportation and measurement based quantum computation, among other areas, bringing several new strategies into NLQC which may be of independent interest.
Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-qubit gate can be implemented by LOBC with ϵ-error using O(log(1/ϵ)) entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as O(1/ϵ). We also consider the family of binary controlled gates on dimensions dA⊗ dB. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of log dB ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when dA= 2. This demonstrates an unbounded gap between the entanglement costs of LOCC and LOBC gate implementation. Whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.
Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f -measure and f -route, the two best studied NLQC tasks, are in fact equivalent under O ( 1 ) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f -measure. For instance, we obtain sub-exponential upper bounds on f -measure for all functions, and efficient protocols for functions in the complexity class M o d k L . Beyond this, we study a number of other examples of NLQC tasks and their relationships.
In noisy intermediate-scale quantum computing, the limited scalability of a single quantum processing unit (QPU) can be extended through distributed quantum computing (DQC), in which one can implement global operations over two QPUs by entanglement-assisted local operations and classical communication. To facilitate this type of DQC in experiments, we need an entanglement-efficient protocol. To this end, we extend the protocol in [Eisert et. al., PRA, 62:052317(2000)] implementing each nonlocal controlled-unitary gate locally with one maximally entangled pair to a packing protocol, which can pack multiple nonlocal controlled-unitary gates locally using one maximally entangled pair. In particular, two types of packing processes are introduced as the building blocks, namely the distributing processes and embedding processes. Each distributing process distributes corresponding gates locally with one entangled pair. The efficiency of entanglement is then enhanced by embedding processes, which merge two non-sequential distributing processes and hence save the entanglement cost. We show that the structure of distributability and embeddability of a quantum circuit can be fully represented by the corresponding packing graphs and conflict graphs. Based on these graphs, we derive heuristic algorithms for finding an entanglement-efficient packing of distributing processes for a given quantum circuit to be implemented by two parties. These algorithms can determine the required number of local auxiliary qubits in the DQC. We apply these algorithms for bipartite DQC of unitary coupled-cluster circuits and find a significant reduction of entanglement cost through embeddings. This method can determine a constructive upper bound on the entanglement cost for the DQC of quantum circuits.
Non-local quantum computation (NLQC) asks two parties to apply a joint operation to their quantum inputs using an entangled resource state and one round of simultaneous quantum communication. NLQC has applications across quantum information, including attacks on quantum position verification, communication complexity, and quantum gravity. Every bipartite unitary has an approximate NLQC protocol with finite entanglement, and exact protocols are known for several structured families. However, it has remained open whether every fixed unitary admits an exact protocol with finite-dimensional resources. We show that, even for two qubits, Haar-almost every unitary does not admit such a protocol, even when the resource state and local operations are tailored to the target. The proof first shows that smooth deformations of an exact protocol can only change its target by local unitaries. For a fixed architecture, semialgebraic geometry limits the exact protocols to finitely many connected families, so each architecture reaches only finitely many local-unitary orbits. Taking the union over all architectures, the exactly implementable unitaries form countably many local-unitary orbits. We also show that some natural targets do not admit a protocol: the controlled phase diag(1,1,1,eiθ)\mathrm{diag}(1,1,1,e^{iθ})diag(1,1,1,eiθ) has no exact protocol with finite-dimensional resources whenever eiθe^{iθ}eiθ is transcendental, for instance for θ=1θ= 1θ=1. Our results also apply to localizable quantum measurements, whose outcome is obtained from local measurements on inputs and a shared entangled resource state without communication. A rank-one projective measurement in a Haar-random basis is almost surely not localizable with a finite-dimensional resource state and finitely many local outcomes.
Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: If coherent nonunitary evolution with renormalization could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP ( U ) as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on O ( 1 ) qubits that is not proportional to a unitary, with the state renormalized after each use of U . We prove that this model is powerful enough to decide every language in PostBQP (equivalently PP ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate U , NHBQP ( U ) = PostBQP = PP . PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a compensating cost limiting its efficiency. Additionally, we study simulation complexity of restricted classes of nonunitary systems by purifying them to postselected unitary evolution in a form preserving system locality. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability Ω ( 2 − poly ( n ) ) . Thus, adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.