Cover Image

Fine-Grained Complexity via Quantum Natural Proofs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Yanlin, Chen, Yilei, Kumar, Rajendra, Patro, Subhasree, Speelman, Florian
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
by: Chen, Yanlin, et al.
Published: (2023)

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

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

Quantum Search With Generalized Wildcards
by: Cornelissen, Arjan, et al.
Published: (2025)

Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)

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

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Quantum Interactive Oracle Proofs
by: Sun, Baocheng, et al.
Published: (2026)

The Round Complexity of Proofs in the Bounded Quantum Storage Model
by: Grilo, Alex B., et al.
Published: (2024)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
by: Chia, Nai-Hui, et al.
Published: (2026)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
by: Grewal, Sabee, et al.
Published: (2025)

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

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

On the Complexity of Decoded Quantum Interferometry
by: Marwaha, Kunal, et al.
Published: (2025)

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

Two Simple Proofs of Müller's Theorem
by: Epstein, Samuel
Published: (2024)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
by: Grewal, Sabee, et al.
Published: (2025)

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

Multi-Prover Interactive Proof Systems with Leakage
by: Asadi, Vahid R., et al.
Published: (2026)

New Approaches to Complexity via Quantum Graphs
by: Culf, Eric, et al.
Published: (2023)

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

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

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
by: Gay, William, et al.
Published: (2026)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
by: Chen, Kean, et al.
Published: (2025)

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

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

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

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

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
by: Chen, Kean, et al.
Published: (2024)

Proof of Hiding Conjecture in Gaussian Boson Sampling
by: Shou, Laura, et al.
Published: (2025)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
Published: (2021)

Proofs of quantum memory
by: Hhan, Minki, et al.
Published: (2025)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
by: Rosenthal, Gregory
Published: (2021)

Complexity of quantum circuits via sensitivity, magic, and coherence
by: Bu, Kaifeng, et al.
Published: (2022)

Accessible Quantum Correlations Under Complexity Constraints
by: Yángüez, Álvaro, et al.
Published: (2026)