Copertina

Exponential improvements to the average-case hardness of BosonSampling

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bouland, Adam, Datta, Ishaun, Fefferman, Bill, Hernandez, Felipe
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Quantum Physics Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

On the hardness of learning ground state entanglement of geometrically local Hamiltonians
di: Bouland, Adam, et al.
Pubblicazione: (2024)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
di: Fefferman, Bill, et al.
Pubblicazione: (2024)

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

Quantum Merlin-Arthur with an internally separable proof
di: Bassirian, Roozbeh, et al.
Pubblicazione: (2024)

Peaked quantum advantage using error correction
di: Deshpande, Abhinav, et al.
Pubblicazione: (2025)

On Certified Randomness from Fourier Sampling or Random Circuit Sampling
di: Bassirian, Roozbeh, et al.
Pubblicazione: (2021)

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

Exact Quantum Circuit Optimization is co-NQP-hard
di: Kjelstrøm, Adam Husted, et al.
Pubblicazione: (2025)

Bosonic Quantum Computational Complexity
di: Chabaud, Ulysse, et al.
Pubblicazione: (2024)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
di: Watts, Adam Bene, et al.
Pubblicazione: (2023)

On the hardness of cloning and connections to representation theory
di: Havlíček, Vojtěch, et al.
Pubblicazione: (2024)

Optimising quantum circuits is generally hard
di: van de Wetering, John, et al.
Pubblicazione: (2023)

Complexity and hardness of random peaked circuits
di: Zhang, Yuxuan
Pubblicazione: (2025)

On the average-case complexity of learning output distributions of quantum circuits
di: Nietner, Alexander, et al.
Pubblicazione: (2023)

DQC1-hardness of estimating correlation functions
di: Moulik, Subhayan Roy, et al.
Pubblicazione: (2024)

Quantum Max-Cut is NP hard to approximate
di: Piddock, Stephen
Pubblicazione: (2025)

How hard is it to verify a classical shadow?
di: Karaiskos, Georgios, et al.
Pubblicazione: (2025)

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
di: Guseynov, Nikita, et al.
Pubblicazione: (2026)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
di: Czégel, András, et al.
Pubblicazione: (2025)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
di: Rayudu, Chaithanya
Pubblicazione: (2024)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
di: Zschetzsche, Lilith, et al.
Pubblicazione: (2026)

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

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
di: Chen, Yu-Zhen Janice, et al.
Pubblicazione: (2025)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
di: Gu, Shouzhen, et al.
Pubblicazione: (2026)

Approximating the quantum value of an LCS game is RE-hard
di: Taller, Aviv, et al.
Pubblicazione: (2025)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
di: Mitosek, Piotr
Pubblicazione: (2024)

(Sub)Exponential Quantum Speedup for Optimization
di: Leng, Jiaqi, et al.
Pubblicazione: (2025)

Exponential speedups in fault-tolerant processing of quantum experiments
di: Kannan, Ishaan, et al.
Pubblicazione: (2026)

Computational hardness of estimating quantum entropies via binary entropy bounds
di: Liu, Yupan
Pubblicazione: (2026)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
di: Grier, Daniel, et al.
Pubblicazione: (2025)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
di: Lykov, Danylo, et al.
Pubblicazione: (2022)

Quantum Event Learning and Gentle Random Measurements
di: Watts, Adam Bene, et al.
Pubblicazione: (2022)

Fault-tolerant compiling of classically hard IQP circuits on hypercubes
di: Hangleiter, Dominik, et al.
Pubblicazione: (2024)

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
di: He, Entong
Pubblicazione: (2024)

Higher moment theory and learnability of bosonic states
di: Iosue, Joseph T., et al.
Pubblicazione: (2025)

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

A slightly improved upper bound for quantum statistical zero-knowledge
di: Gall, François Le, et al.
Pubblicazione: (2025)

An efficient construction of Raz's two-source randomness extractor with improved parameters
di: Foreman, Cameron, et al.
Pubblicazione: (2025)

Random Circuit Sampling: Fourier Expansion and Statistics
di: Kalai, Gil, et al.
Pubblicazione: (2024)