Quantum Lower Bounds by Entropy Numbers

2006/11/30 by Stefan Heinrich, Heinrich, Stefan
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0611294

Submitted to J. Complexity

arxiv created 2006/11/30 · openalex publication_date 2006/11/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use entropy numbers in combination with the polynomial method to derive a new general lower bound for the n-th minimal error in the quantum setting of information-based complexity. As an application, we improve some lower bounds on quantum approximation of embeddings between finite dimensional L_p spaces and of Sobolev embeddings.

Citations

• Optimal lower bounds for quantum automata and random access codes
• Quantum Lower Bounds by Polynomials

Related

• Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
• Classical lower bounds from quantum upper bounds
• Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces
• Entropy lower bounds of quantum decision tree complexity
• An Extended Coding Theorem with Application to Quantum Complexities