Cover Image

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Balliu, Alkida, Coupette, Corinna, Cruciani, Antonio, d'Amore, Francesco, Equi, Massimo, Lievonen, Henrik, Modanese, Augusto, Olivetti, Dennis, Suomela, Jukka
Format:	Preprint
Published:	2025
Subjects:	Distributed, Parallel, and Cluster Computing Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Distributed Quantum Advantage for Local Problems
by: Balliu, Alkida, et al.
Published: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

Distributed Computation with Local Advice
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)

Model-Agnostic Approximation of Constrained Forest Problems
by: Coupette, Corinna, et al.
Published: (2024)

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

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

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

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

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

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
by: Gao, Xun, et al.
Published: (2021)

Dequantization Barriers for Guided Stoquastic Hamiltonians
by: Hamoudi, Yassine, et al.
Published: (2026)

Dequantization and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Dequantizing Short-Path Quantum Algorithms
by: Gall, François Le, et al.
Published: (2026)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
by: Sakamoto, Kazuki, et al.
Published: (2025)

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

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)

Embedding arbitrary Boolean circuits into fungal automata with arbitrary update sequences
by: Goles, Eric, et al.
Published: (2026)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

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

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

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
by: Lassota, Alexandra, et al.
Published: (2026)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

Formal Framework for Quantum Advantage
by: Buhrman, Harry, et al.
Published: (2025)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
by: Büsing, Christina, et al.
Published: (2025)