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.
Circuit knitting, a method for connecting quantum circuits across multiple processors to simulate nonlocal quantum operations, is a promising approach for distributed quantum computing. While various techniques have been developed for circuit knitting, we uncover fundamental limitations to the scalability of this technology. We prove that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic, even with the asymptotic amount of resources using the parallel cut strategy. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we develop the faithful lower bounds for the regularized sampling overhead based on channels' $\ensuremath{\kappa}$ entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasiprobability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.
Entanglement-assisted discrimination of orthogonal quantum states exhibiting quantum nonlocality is a frontier topic in quantum information theory. In this paper, we investigate the role of multipartite entanglement and develop resource-efficient LOCC discrimination protocols for nonlocal sets of orthogonal states, including multipartite orthogonal product-state sets and entangled-state sets with different nonlocal features. By incorporating controlled-NOT (CNOT) operations into the discrimination procedure, we construct protocols for genuinely nonlocal GHZ bases in four- and five-qubit systems that require only a single EPR pair. For the same target sets, we compare different entanglement-assisted schemes and identify those with lower entanglement consumption. We further observe that, on average, protocols avoiding teleportation consume fewer resources than teleportation-based approaches. In addition, when higher-partite GHZ-type resources (with
n>3) are available among suitable subsystems, they can in some cases reduce the overall entanglement cost. Our results highlight the operational significance of multipartite entanglement and provide practical protocols for the local discrimination of orthogonal state sets exhibiting quantum nonlocality.
Distributed architectures extend quantum simulation of many-body dynamics beyond the reach of any single processor, with shared entanglement mediating interactions between spatially separated devices. Conventional implementations rely on quantum teleportation, which provides a universal realization of nonlocal operations but incurs a fixed entanglement cost per gate, irrespective of its strength. This becomes increasingly inefficient in product formula simulation, where higher accuracy requires ever more numerous, yet progressively weaker, nonlocal rotations, causing the entanglement cost to diverge in the high-accuracy limit. Here we introduce a simple repeat-until-success protocol that makes entanglement consumption adaptive to interaction strength. Incorporating this primitive into distributed product formulas yields a total entanglement cost that scales linearly with evolution time and remains independent of Trotter error. A matching lower bound from quantum communication complexity proves this time scaling to be optimal, establishing a resource-efficient foundation for high-accuracy quantum simulation across networked processors.