Copertina

A simple lower bound for the complexity of estimating partition functions on a quantum computer

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chen, Zherui, Nannicini, Giacomo
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Quantum Physics Computational Complexity Data Structures and Algorithms Statistics Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Optimal lower bounds for quantum state tomography
di: Scharnhorst, Thilo, et al.
Pubblicazione: (2025)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
di: Allcock, Jonathan, et al.
Pubblicazione: (2024)

Clifford testing: algorithms and lower bounds
di: Hinsche, Marcel, et al.
Pubblicazione: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
di: Apers, Simon, et al.
Pubblicazione: (2021)

On estimating the trace of quantum state powers
di: Liu, Yupan, et al.
Pubblicazione: (2024)

On estimating the quantum $\ell_α$ distance
di: Liu, Yupan, et al.
Pubblicazione: (2025)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
di: Fu, Daniel, et al.
Pubblicazione: (2026)

Model-agnostic super-resolution in high dimensions
di: Chen, Xi, et al.
Pubblicazione: (2025)

Robust and optimal loading of general classical data into quantum computers
di: Zhang, Xiao-Ming
Pubblicazione: (2024)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
di: Yu, Xifan, et al.
Pubblicazione: (2024)

Stable Algorithms Lower Bounds for Estimation
di: Yu, Xifan, et al.
Pubblicazione: (2026)

Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering
di: Philip, Aby, et al.
Pubblicazione: (2023)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
di: Sarkar, Rohit Sarma, et al.
Pubblicazione: (2024)

Amplitude amplification and estimation require inverses
di: Tang, Ewin, et al.
Pubblicazione: (2025)

Beating full state tomography for unentangled spectrum estimation
di: Pelecanos, Angelos, et al.
Pubblicazione: (2025)

Elfs, transducers and quantum walks
di: Apers, Simon, et al.
Pubblicazione: (2026)

Testing and learning structured quantum Hamiltonians
di: Arunachalam, Srinivasan, et al.
Pubblicazione: (2024)

Certifying and learning local quantum Hamiltonians
di: Bluhm, Andreas, et al.
Pubblicazione: (2026)

Certifying and learning quantum Ising Hamiltonians
di: Bluhm, Andreas, et al.
Pubblicazione: (2025)

Fast quantum algorithm for differential equations
di: Bagherimehrab, Mohsen, et al.
Pubblicazione: (2023)

Optimal learning of quantum channels in diamond distance
di: Mele, Antonio Anna, et al.
Pubblicazione: (2025)

Directed st-connectivity with few paths is in quantum logspace
di: Apers, Simon, et al.
Pubblicazione: (2024)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
di: Harvey, Nicholas, et al.
Pubblicazione: (2024)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
di: R., Abhishek Hegade K., et al.
Pubblicazione: (2025)

Testing Convex Truncation
di: De, Anindya, et al.
Pubblicazione: (2023)

Strong Low Degree Hardness for the Number Partitioning Problem
di: Mallarapu, Rushil, et al.
Pubblicazione: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
di: Sohn, Youngtak, et al.
Pubblicazione: (2025)

Quantum Multi-Level Estimation of Functionals of Discrete Distributions
di: Chen, Kean, et al.
Pubblicazione: (2026)

Detection of local geometry in random graphs: information-theoretic and computational limits
di: Bok, Jinho, et al.
Pubblicazione: (2026)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
di: Abbas, Amira, et al.
Pubblicazione: (2025)

Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
di: Allcock, Jonathan, et al.
Pubblicazione: (2025)

Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
di: Wang, Qisheng
Pubblicazione: (2024)

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
di: Wang, Qisheng, et al.
Pubblicazione: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
di: Singer, Noah G.
Pubblicazione: (2025)

Statistical inference of a ranked community in a directed graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Strict Hierarchy for Quantum Channel Certification to Unitary
di: Chen, Kean, et al.
Pubblicazione: (2026)

Positive bias makes tensor-network contraction tractable
di: Jiang, Jiaqing, et al.
Pubblicazione: (2024)

Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation
di: Chen, Sitan, et al.
Pubblicazione: (2024)

The communication complexity of distributed estimation
di: Gopalan, Parikshit, et al.
Pubblicazione: (2025)