Imagen de Portada

Why Philosophers Should Care About Computational Complexity

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Aaronson, Scott
Formato:	Preprint
Publicado:	2011
Materias:	Computational Complexity Quantum Physics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
por: Aaronson, Scott, et al.
Publicado: (2023)

The Acrobatics of BQP
por: Aaronson, Scott, et al.
Publicado: (2021)

Improved separation between quantum and classical computers for sampling and functional tasks
por: Marshall, Simon C., et al.
Publicado: (2024)

A Relativizing MIP for BQP
por: Aaronson, Scott, et al.
Publicado: (2026)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
por: Aaronson, Scott, et al.
Publicado: (2024)

Pseudo-deterministic Quantum Algorithms
por: Aaronson, Hugo, et al.
Publicado: (2026)

Bosonic Quantum Computational Complexity
por: Chabaud, Ulysse, et al.
Publicado: (2024)

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

On the Computational Complexity of Schrödinger Operators
por: Zheng, Yufan, et al.
Publicado: (2024)

Quantum Channel Testing in Average-Case Distance
por: Rosenthal, Gregory, et al.
Publicado: (2024)

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

The Complexity of Stoquastic Sparse Hamiltonians
por: Grilo, Alex B., et al.
Publicado: (2026)

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

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

The Communication Complexity of Approximating Matrix Rank
por: Sherstov, Alexander A., et al.
Publicado: (2024)

Complexity and hardness of random peaked circuits
por: Zhang, Yuxuan
Publicado: (2025)

The Power of Lorentz Quantum Computer
por: Zhang, Qi, et al.
Publicado: (2024)

On the Complexity of the Succinct State Local Hamiltonian Problem
por: Waite, Gabriel, et al.
Publicado: (2025)

A Brief Introduction to Quantum Query Complexity
por: Hamoudi, Yassine
Publicado: (2025)

A Note on the Complexity of the Spectral Gap Problem
por: Yirka, Justin
Publicado: (2025)

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

On the Complexity of Pure-State Consistency of Local Density Matrices
por: Kamminga, Jonas, et al.
Publicado: (2024)

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
por: Waite, Gabriel, et al.
Publicado: (2025)

Complexity Classification of Product State Problems for Local Hamiltonians
por: Kallaugher, John, et al.
Publicado: (2024)

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

Fine-Grained Complexity via Quantum Natural Proofs
por: Chen, Yanlin, et al.
Publicado: (2025)

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

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

Computational complexity of isometric tensor network states
por: Malz, Daniel, et al.
Publicado: (2024)

The Computational Advantage of MIP* Vanishes in the Presence of Noise
por: Dong, Yangjing, et al.
Publicado: (2023)

Computational aspects of the trace norm contraction coefficient
por: Delsol, Idris, et al.
Publicado: (2025)

The Space-Time Cost of Purifying Quantum Computations
por: Zhandry, Mark
Publicado: (2024)

Modifications of Quantum Computation and Adaptive Queries to PP
por: Miloschewsky, David, et al.
Publicado: (2025)

Complexity-theoretic foundations of BosonSampling with a linear number of modes
por: Bouland, Adam, et al.
Publicado: (2023)

New Quantum Algorithms for Computing Quantum Entropies and Distances
por: Wang, Qisheng, et al.
Publicado: (2022)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
por: Cade, Chris, et al.
Publicado: (2022)

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
por: Hiromasa, Ryo, et al.
Publicado: (2022)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
por: Miloschewsky, David, et al.
Publicado: (2024)

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

Complexity of Contextuality
por: Yianni, Theodoros, et al.
Publicado: (2025)