Distributed Trotterization with optimal time-scaling entanglement cost

Distributed quantum computing allows spatially separated processors to perform collective quantum simulations by sharing entanglement. In conventional approaches, nonlocal operations are implemented via quantum teleportation, which consumes a fixed amount of entanglement per gate. This becomes highly inefficient in product formula simulations, where higher accuracy requirements necessitate an increasing number of progressively weaker nonlocal rotations, causing the total entanglement cost to diverge.

This paper presents a repeat-until-success (RUS) protocol that replaces fixed-cost teleportation with an adaptive strategy. By using weakly entangled resource states whose entanglement is matched to the specific strength of the target rotation, the protocol ensures that the entanglement cost remains proportional to the interaction strength. If a rotation attempt fails, the protocol uses a stronger resource state in the next round, but because these rounds are reached with exponentially decreasing probability, the average entanglement cost remains low.

When incorporated into distributed product formulas, this RUS-based approach decouples the entanglement cost from the number of Trotter steps. The total entanglement cost scales linearly with the total evolution time and is independent of the target simulation error. The authors prove that this linear time scaling is optimal by establishing a matching lower bound using quantum communication complexity. This result demonstrates that high-accuracy distributed simulations can be achieved without the prohibitive resource overheads associated with standard teleportation-based methods.