Asynchronous Quantum Distributed Computing: Causality, Snapshots, and Global Operations

Referee: [QGO Algorithm analysis] The analysis of the QGO algorithm (described in the abstract and presumably in the main technical sections) asserts that Lamport causality arguments carry over, but does not provide an explicit inductive argument or lemma showing that the happened-before relation on recorded local outcomes is preserved when the underlying state is entangled; a local measurement in the snapshot phase can instantaneously alter the reduced density operator on a remote node, and the manuscript must demonstrate that the classical message-ordering mechanism still enforces the required causal constraints for non-product states.

Authors: We agree that making the inductive argument explicit would improve clarity. The happened-before relation in our model is defined solely on the classical events: the sending and receiving of messages and the local actions, including the recording of measurement outcomes. The QGO algorithm uses the same message-passing structure as Chandy-Lamport to coordinate when each node performs its local operation (e.g., measurement for a snapshot). Although a local measurement can change the reduced density matrix of a remote entangled system, this does not affect the causal ordering of the events themselves, which are determined by the classical communication. The correctness relies on the fact that the local operations are executed in an order consistent with the happened-before relation defined by the messages, ensuring that the collected local outcomes correspond to a consistent global view as per the specification. In the revised manuscript, we will add a dedicated lemma that proves by induction over the happened-before partial order that the recorded outcomes respect the causal constraints, explicitly addressing non-product states by noting that the proof does not depend on the state being separable. revision: yes

Referee: [Formal specification of global operations] The weakest assumption—that any target global operation decomposes into a collection of local operations whose execution can be coordinated exactly as in the classical snapshot—needs to be stated as a formal precondition on the class of admissible quantum global operations; without this, the reduction from the quantum claim to the classical Chandy-Lamport proof is incomplete, as the manuscript does not address operations whose local components are not independently executable without reference to the global entangled state.

Authors: We concur that formalizing this assumption is necessary for rigor. The manuscript focuses on decomposable operations, such as global measurements in a product basis, where each local measurement can be performed independently once the coordination messages dictate the timing. However, we recognize that not all conceivable global operations may satisfy this (e.g., those requiring adaptive local operations based on the global state in a non-local way). In the revision, we will add a formal definition in the model section: A global operation is decomposable if it can be realized by a set of local quantum operations, each executable on the local subsystem using only local information and the coordination signals from the algorithm, without needing to access the global state at runtime. This precondition allows the direct reduction to the classical snapshot algorithm's correctness. We will also discuss the scope, noting that this covers important cases like quantum snapshots and certain global unitaries that decompose locally. revision: yes