Quantum Analog of Shannon's Lower Bound Theorem

2023/08/24 by Saugata Basu, Laxmi Parida, Basu, Saugata +1 · 1 citation
Computer Science · #81P68 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Numerical Methods and Algorithms #Polynomial and algebraic computation #Primary 68Q12 #Quantum Physics (quant-ph) #Secondary 14P10

paper · pdf · doi:10.48550/arxiv.2308.13091

openalex publication_date 2023/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Shannon proved that almost all Boolean functions require a circuit of size Θ(2ⁿ/n). We prove a quantum analog of this classical result. Unlike in the classical case the number of quantum circuits of any fixed size that we allow is uncountably infinite. Our main tool is a classical result in real algebraic geometry bounding the number of realizable sign conditions of any finite set of real polynomials in many variables.

Cited by

• Counting Martingales for Measure and Dimension in Complexity Classes

Related

• Quantum Formulas: a Lower Bound and Simulation
• An Almost-Quadratic Lower Bound for Quantum Formula Size
• Quantum Lower Bounds by Polynomials
• A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth
• Quantum Meets the Minimum Circuit Size Problem