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:2610.15601

A Quantum Analogue of the Covering Lemma: Limits of Exact Anonymous Computation

Giuseppe Di Molfetta, Petra Camilli

quant-phcs.DCcs.DMSubmitted Oct 11, 2026• Announced Oct 13, 2026• 0 citations
arXivHTMLPDF

Abstract

Can quantum communication determine the size of an anonymous network when no size bound is known? Classical impossibility proofs rely on the covering lemma: an execution can be reproduced on a larger network with the same local structure. Quantum interference invalidates this argument - a measurement record possible on a network can become impossible on a cover. We show that the impossibility of exact counting nevertheless survives. Our main result is a quantum analogue of the covering lemma that preserves local possibilities rather than complete executions. Within a cyclic covering family, every local measurement outcome possible at a node remains possible at a corresponding node in every sufficiently large network. This holds even after information has travelled around the smaller network, beyond the reach of a simple locality argument. We extend the principle to the universal covering tree and finite covers with sufficiently long cycles. The proof combines tensor-network methods with graph coverings: a common representation across network sizes turns normalization into a constraint on which local outcomes can occur. For uniform synchronous protocols with independently prepared nodes, this support-lifting principle rules out zero-error counting and even the production of a guaranteed finite size bound on anonymous rings and the other cyclic covering families considered here. It also rules out exact leader election with termination in finite time with probability one on these families. Measurements, classical control, and local memory growing with time are allowed; no predetermined running-time bound is assumed. Quantum interference thus defeats execution lifting without enabling infallible certification of network size.

AI Summary

Can quantum communication enable exact counting or leader election in an anonymous network without any known size bound? Classical impossibility proofs lift complete executions to covering graphs, but quantum interference can invalidate that step. This paper replaces execution lifting with a theorem about local-state supports. For a connected cyclic covering family $\mathcal N_m$, the main result is $\operatorname{supp}\rho_k(v,s)\subseteq\operatorname{supp}\rho_m(v,s)$ for every $k\geq1$ and $m\geq2s+1$. Thus any local outcome possible after $s$ rounds on one member remains possible on every sufficiently large member, even when information has already traversed the smaller network. The proof combines a uniform finite-horizon dilation, a common matrix-product representation across cover sizes, normalization constraints on its transfer spectrum, and finite-time locality. Support inclusion also holds into the universal covering tree and finite covers of girth greater than $2s$. A two-round example with orthogonal local states on $C_2$ and $C_4$ prevents uniformly replacing the threshold by $2s$. Consequently, zero-error protocols cannot output an exact size or any guaranteed finite size bound on admissible cyclic towers. A leader-to-counting reduction excludes exact leader election, including almost-sure finite termination without a predetermined deadline. The results assume lift-uniform synchronous dynamics, independent node preparation, and finite local resources at each fixed horizon, uniformly across cover sizes. Initially shared correlations and size-dependent resources are excluded. The theorem gives no quantitative probability bound for bounded-error computation; arbitrary asynchronous support lifting and a full characterization of exact anonymous quantum computation remain open.

No sign of AI-generated textAI use disclosed
AI tools were used for double checking proofs and improve drafting.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Exact Quantum Algorithms for the Leader Election Problem

Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto

This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded.

arXiv:0712.4213•ACM Transactions on Computation Theory•Mar 1, 2012•74 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

Computing on Anonymous Quantum Network

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

The anonymous network model was introduced by Angluin in [STOC '80, to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties.In this model, all parties with the same number of communication links are identical.When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party.It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication.This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed [TOCT, vol.4,no.1, article 1].The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty.This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election.The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.

arXiv:1001.5307•Chicago Journal of Theoretical Computer Science•Jan 1, 2014•8 citations

Simpler Exact Leader Election via Quantum Reduction

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

The anonymous network model was introduced by Angluin in (STOC '80, pages 82-93) to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties. In this model, all parties with the same number of communication links are identical. When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party. It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication. This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed (TOCT, vol.4, no.1, article 1). The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty. This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election. The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.

Chicago Journal of Theoretical Computer Science•Jan 1, 2014•3 citations

What Can be Observed Locally? Round-based Models for Quantum Distributed Computing

Cyril Gavoille, Adrian Kosowski, Markiewicz, Marcin

Recently, several claims have been made that certain fundamental problems of distributed computing, including Leader Election and Distributed Consensus, begin to admit feasible and efficient solutions when the model of distributed computation is extended so as to apply quantum processing. This has been achieved in one of two distinct ways: (1) by initializing the system in a quantum entangled state, and/or (2) by applying quantum communication channels. In this paper, we explain why some of these prior claims are misleading, in the sense that they rely on changes to the model unrelated to quantum processing. On the positive side, we consider the aforementioned quantum extensions when applied to Linial's well-established LOCAL model of distributed computing. For both types of extensions, we put forward valid proof-of-concept examples of distributed problems whose round complexity is in fact reduced through genuinely quantum effects, in contexts which do not depend on the anonymity of nodes. Finally, we show that even the quantum variants of the LOCAL model have non-trivial limitations, captured by a very simple (purely probabilistic) notion which we call "physical locality" (PLOCAL). While this is strictly weaker than the "computational locality" of the classical LOCAL model, it nevertheless implies that for many distributed combinatorial optimization problems, such as Maximal Independent Set, the best currently known lower time bounds cannot be broken by applying quantum processing, in any conceivable way.

arXiv:0903.1133•Mar 6, 2009•6 citations

Operational Capacity Bounds for Distinguishable Decoherent Histories: Environmental Records, Observer Access, and Finite-Error Discrimination

David Reardon

Abstract Decoherent-histories methods identify time-extended alternatives whose diagonal weights may support probabilistic interpretation, while environmental-record approaches ask which alternatives a specified observer can recover. We formulate their intersection as a finite branch-record packing problem generated from one cross-branch construction. A codebook is admissible only if its declared coarse-graining obeys a bounded probability-sum-rule error and its accessible states can be decoded under a specified observer policy with finite error. Uniform reweighting defines a geometric packing number; a communication interpretation additionally requires a preparation instrument. Retrospective resolution is stricter: the base history family is exhaustive, selected histories must cover sufficient physical diagonal weight and be individually recoverable, and the same declared quantum-to-classical measurement channel used for decoding must preserve approximate consistency after histories are refined by its registered outcomes. This measurement-refined condition quantitatively controls the difference between the actual outcome distribution and the normalized diagonal classical-quantum prediction. For uniform branch-record packing and its communication realizations, general converses follow from accessible dimension, fixed outcome count, Holevo-Fano information, and hypothesis testing. Exact models quantify record compression, access, memory, measurement policy, temporal dependence, and shared latent errors. In a jointly realized four-bit benchmark, scalar consistency and recovery admit six histories, whereas direct measurement-refined consistency under the declared local Helstrom instrument admits four at the same tolerances. Finite-sample procedures distinguish held-out recovery achievability, structure-conditional consistency certification, structural converses, independently constructed parameter intervals, and abstention.

•Jul 31, 2026•0 citations
Can quantum communication determine the size of an anonymous network when no size bound is known? Classical impossibility proofs rely on the covering lemma: an execution can be reproduced on a larger network with the same local structure. Quantum interference invalidates this argument - a measurement record possible on a network can become impossible on a cover. We show that the impossibility of exact counting nevertheless survives. Our main result is a quantum analogue of the covering lemma that preserves local possibilities rather than complete executions. Within a cyclic covering family, every local measurement outcome possible at a node remains possible at a corresponding node in every sufficiently large network. This holds even after information has travelled around the smaller network, beyond the reach of a simple locality argument. We extend the principle to the universal covering tree and finite covers with sufficiently long cycles. The proof combines tensor-network methods with graph coverings: a common representation across network sizes turns normalization into a constraint on which local outcomes can occur. For uniform synchronous protocols with independently prepared nodes, this support-lifting principle rules out zero-error counting and even the production of a guaranteed finite size bound on anonymous rings and the other cyclic covering families considered here. It also rules out exact leader election with termination in finite time with probability one on these families. Measurements, classical control, and local memory growing with time are allowed; no predetermined running-time bound is assumed. Quantum interference thus defeats execution lifting without enabling infallible certification of network size.
Can quantum communication enable exact counting or leader election in an anonymous network without any known size bound? Classical impossibility proofs lift complete executions to covering graphs, but quantum interference can invalidate that step. This paper replaces execution lifting with a theorem about local-state supports.
For a connected cyclic covering family Nm\mathcal N_mNm​, the main result is supp⁡ρk(v,s)⊆supp⁡ρm(v,s)\operatorname{supp}\rho_k(v,s)\subseteq\operatorname{supp}\rho_m(v,s)suppρk​(v,s)⊆suppρm​(v,s) for every k≥1k\geq1k≥1 and m≥2s+1m\geq2s+1m≥2s+1. Thus any local outcome possible after sss rounds on one member remains possible on every sufficiently large member, even when information has already traversed the smaller network. The proof combines a uniform finite-horizon dilation, a common matrix-product representation across cover sizes, normalization constraints on its transfer spectrum, and finite-time locality. Support inclusion also holds into the universal covering tree and finite covers of girth greater than 2s2s2s. A two-round example with orthogonal local states on C2C_2C2​ and C4C_4C4​ prevents uniformly replacing the threshold by 2s2s2s.
Consequently, zero-error protocols cannot output an exact size or any guaranteed finite size bound on admissible cyclic towers. A leader-to-counting reduction excludes exact leader election, including almost-sure finite termination without a predetermined deadline.
The results assume lift-uniform synchronous dynamics, independent node preparation, and finite local resources at each fixed horizon, uniformly across cover sizes. Initially shared correlations and size-dependent resources are excluded. The theorem gives no quantitative probability bound for bounded-error computation; arbitrary asynchronous support lifting and a full characterization of exact anonymous quantum computation remain open.
This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded.
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.
The anonymous network model was introduced by Angluin in [STOC '80, to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties.In this model, all parties with the same number of communication links are identical.When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party.It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication.This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed [TOCT, vol.4,no.1, article 1].The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty.This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election.The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.
The anonymous network model was introduced by Angluin in (STOC '80, pages 82-93) to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties. In this model, all parties with the same number of communication links are identical. When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party. It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication. This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed (TOCT, vol.4, no.1, article 1). The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty. This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election. The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.
Recently, several claims have been made that certain fundamental problems of distributed computing, including Leader Election and Distributed Consensus, begin to admit feasible and efficient solutions when the model of distributed computation is extended so as to apply quantum processing. This has been achieved in one of two distinct ways: (1) by initializing the system in a quantum entangled state, and/or (2) by applying quantum communication channels. In this paper, we explain why some of these prior claims are misleading, in the sense that they rely on changes to the model unrelated to quantum processing. On the positive side, we consider the aforementioned quantum extensions when applied to Linial's well-established LOCAL model of distributed computing. For both types of extensions, we put forward valid proof-of-concept examples of distributed problems whose round complexity is in fact reduced through genuinely quantum effects, in contexts which do not depend on the anonymity of nodes. Finally, we show that even the quantum variants of the LOCAL model have non-trivial limitations, captured by a very simple (purely probabilistic) notion which we call "physical locality" (PLOCAL). While this is strictly weaker than the "computational locality" of the classical LOCAL model, it nevertheless implies that for many distributed combinatorial optimization problems, such as Maximal Independent Set, the best currently known lower time bounds cannot be broken by applying quantum processing, in any conceivable way.
Abstract Decoherent-histories methods identify time-extended alternatives whose diagonal weights may support probabilistic interpretation, while environmental-record approaches ask which alternatives a specified observer can recover. We formulate their intersection as a finite branch-record packing problem generated from one cross-branch construction. A codebook is admissible only if its declared coarse-graining obeys a bounded probability-sum-rule error and its accessible states can be decoded under a specified observer policy with finite error. Uniform reweighting defines a geometric packing number; a communication interpretation additionally requires a preparation instrument. Retrospective resolution is stricter: the base history family is exhaustive, selected histories must cover sufficient physical diagonal weight and be individually recoverable, and the same declared quantum-to-classical measurement channel used for decoding must preserve approximate consistency after histories are refined by its registered outcomes. This measurement-refined condition quantitatively controls the difference between the actual outcome distribution and the normalized diagonal classical-quantum prediction. For uniform branch-record packing and its communication realizations, general converses follow from accessible dimension, fixed outcome count, Holevo-Fano information, and hypothesis testing. Exact models quantify record compression, access, memory, measurement policy, temporal dependence, and shared latent errors. In a jointly realized four-bit benchmark, scalar consistency and recovery admit six histories, whereas direct measurement-refined consistency under the declared local Helstrom instrument admits four at the same tolerances. Finite-sample procedures distinguish held-out recovery achievability, structure-conditional consistency certification, structural converses, independently constructed parameter intervals, and abstention.