Cover Image

Distributed Quantum Advantage for Local Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Balliu, Alkida, Brandt, Sebastian, Coiteux-Roy, Xavier, d'Amore, Francesco, Equi, Massimo, Gall, François Le, Lievonen, Henrik, Modanese, Augusto, Olivetti, Dennis, Renou, Marc-Olivier, Suomela, Jukka, Tendick, Lucas, Veeren, Isadora
Format:	Preprint
Published:	2024
Subjects:	Distributed, Parallel, and Cluster Computing Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
by: Balliu, Alkida, et al.
Published: (2025)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
by: Balliu, Alkida, et al.
Published: (2025)

No distributed quantum advantage for approximate graph coloring
by: Coiteux-Roy, Xavier, et al.
Published: (2023)

Online Locality Meets Distributed Quantum Computing
by: Akbari, Amirreza, et al.
Published: (2024)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
by: Balliu, Alkida, et al.
Published: (2025)

Distributed Algorithms for Potential Problems
by: Balliu, Alkida, et al.
Published: (2025)

On the Universality of Round Elimination Fixed Points
by: Balliu, Alkida, et al.
Published: (2025)

Is a LOCAL algorithm computable?
by: Cruciani, Antonio, et al.
Published: (2026)

Shared Randomness Helps with Local Distributed Problems
by: Balliu, Alkida, et al.
Published: (2024)

Distributed Computation with Local Advice
by: Balliu, Alkida, et al.
Published: (2024)

Tight Lower Bounds in the Supported LOCAL Model
by: Balliu, Alkida, et al.
Published: (2024)

Local problems in trees across a wide range of distributed models
by: Dhar, Anubhav, et al.
Published: (2024)

Towards Fully Automatic Distributed Lower Bounds
by: Balliu, Alkida, et al.
Published: (2024)

Completing the Node-Averaged Complexity Landscape of LCLs on Trees
by: Balliu, Alkida, et al.
Published: (2024)

On the Limits of Distributed Quantum Computing
by: d'Amore, Francesco
Published: (2025)

Orientation does not help with 3-coloring a grid in online-LOCAL
by: Boudier, Thomas, et al.
Published: (2025)

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
by: Balliu, Alkida, et al.
Published: (2026)

Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
by: Balliu, Alkida, et al.
Published: (2024)

On the Node-Averaged Complexity of Locally Checkable Problems on Trees
by: Balliu, Alkida, et al.
Published: (2023)

Phase transition of the 3-majority opinion dynamics with noisy interactions
by: d'Amore, Francesco, et al.
Published: (2021)

Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
by: Balliu, Alkida, et al.
Published: (2024)

Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions
by: d'Amore, Francesco, et al.
Published: (2020)

Classification of Local Optimization Problems in Directed Cycles
by: Boudier, Thomas, et al.
Published: (2026)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
by: Hasegawa, Atsuya, et al.
Published: (2025)

Search via Parallel Lévy Walks on $\mathbb{Z}^2$
by: Clementi, Andrea, et al.
Published: (2020)

On the $h$-majority dynamics with many opinions
by: d'Amore, Francesco, et al.
Published: (2025)

DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus
by: d'Amore, Francesco, et al.
Published: (2026)

It does not matter how you define locally checkable labelings
by: Cruciani, Antonio, et al.
Published: (2026)

Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
by: Gall, François Le, et al.
Published: (2025)

The genuinely multipartite nonlocality of graph states is model-dependent
by: Coiteux-Roy, Xavier, et al.
Published: (2024)

Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
by: da Cunha, Arthur, et al.
Published: (2023)

2-Coloring Cycles in One Round
by: Flin, Maxime, et al.
Published: (2026)

Testing Spreading Behavior in Networks with Arbitrary Topologies
by: Modanese, Augusto, et al.
Published: (2023)

Meta-Theorems for Cuttable Distributed Problems
by: Bonamy, Marthe, et al.
Published: (2026)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
by: Gall, François Le
Published: (2024)

Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
by: Gupta, Chetan, et al.
Published: (2024)

Characterizing high-dimensional quantum contextuality
by: Yu, Xiao-Dong, et al.
Published: (2022)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
by: Delavenne, Hugo, et al.
Published: (2024)

Thomson problem on a spherical cap
by: Amore, Paolo
Published: (2025)