Imagen de Portada

The Quantumly Fast and the Classically Forrious

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Canonne, Clément L., Chen, Kenny, Mestre, Julián
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Interactive Proofs For Distribution Testing With Conditional Oracles
por: Biswas, Ari, et al.
Publicado: (2025)

Communication with Imperfectly Shared Randomness
por: Canonne, Clément L., et al.
Publicado: (2014)

Uniformity testing when you have the source code
por: Canonne, Clément L., et al.
Publicado: (2024)

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design
por: Canonne, Clément L., et al.
Publicado: (2025)

Separating Quantum and Classical Advice with Good Codes
por: Bostanci, John, et al.
Publicado: (2026)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
por: Agarwal, Avantika, et al.
Publicado: (2024)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
por: Guan, Ziyi, et al.
Publicado: (2023)

Improved Circuit Lower Bounds and Quantum-Classical Separations
por: Grewal, Sabee, et al.
Publicado: (2024)

Classical Simulability of Quantum Circuits with Shallow Magic Depth
por: Zhang, Yifan, et al.
Publicado: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
por: Jeronimo, Fernando Granha, et al.
Publicado: (2024)

Quantum Complexity vs Classical Complexity: A Survey
por: Vaezi, Arash, et al.
Publicado: (2023)

Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions
por: Chen, Ying, et al.
Publicado: (2025)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
por: Wu, Xudong, et al.
Publicado: (2025)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
por: Sankar, Kaushik
Publicado: (2025)

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
por: Yang, Guangxu, et al.
Publicado: (2025)

Classical Verification of Quantum Learning
por: Caro, Matthias C., et al.
Publicado: (2023)

Quantum Pseudorandomness and Classical Complexity
por: Kretschmer, William
Publicado: (2021)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
por: Li, Xingjian, et al.
Publicado: (2023)

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
por: Yang, Guangxu, et al.
Publicado: (2026)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
por: Khadiev, Kamil, et al.
Publicado: (2017)

Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms
por: Do, Phuc Hao, et al.
Publicado: (2025)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
por: Cornelissen, Arjan, et al.
Publicado: (2022)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
por: Nelson, Jon, et al.
Publicado: (2024)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
por: Carbonnel, Clément
Publicado: (2026)

A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream
por: Kordonowy, Steven, et al.
Publicado: (2026)

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
por: Zhang, Zhihan, et al.
Publicado: (2024)

Semi-Classical Subspaces, The No Synchronization Law, and More
por: Epstein, Samuel
Publicado: (2024)

Certificate Games and Consequences for the Classical Adversary Bound
por: Chakraborty, Sourav, et al.
Publicado: (2022)

Fast interpolation and multiplication of unbalanced polynomials
por: Giorgi, Pascal, et al.
Publicado: (2024)

Fast polynomial computations with space constraints
por: Grenet, Bruno
Publicado: (2025)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
por: Zhang, Yifan F., et al.
Publicado: (2025)

The Line Traveling Salesman and Repairman Problem with Collaboration
por: Golak, Julian, et al.
Publicado: (2025)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
por: Huang, Jeremy Ahrens, et al.
Publicado: (2024)

Graphs without a partition into two proportionally dense subgraphs
por: Bazgan, Cristina, et al.
Publicado: (2018)

On the Classical Hardness of the Semidirect Discrete Logarithm Problem in Finite Groups
por: Arif, Mohammad Ferry Husnil, et al.
Publicado: (2025)

Classically Spoofing System Linear Cross Entropy Score Benchmarking
por: Tanggara, Andrew, et al.
Publicado: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
por: Buhrman, Harry, et al.
Publicado: (2024)

Toward Separating QMA from QCMA with a Classical Oracle
por: Zhandry, Mark
Publicado: (2024)

Quantum Fast Implementation of Functional Bootstrapping and Private Information Retrieval
por: Ma, Guangsheng, et al.
Publicado: (2024)

Classical simulability of quantum circuits followed by sparse classical post-processing
por: Takahashi, Yasuhiro, et al.
Publicado: (2026)