2003/02/03 by Farid Ablayev, Ablayev, Farid, Aida Gainutdinova +4
Computer Science · Physics and Astronomy · #Advanced Data Storage Technologies #FOS: Physical sciences #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0302022
arxiv created 2003/02/03 · openalex publication_date 2003/02/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study a model of a Quantum Branching Program (QBP) and investigate its computational power. We prove a general lower bound on the width of read-once QBPs, which we show to be almost tight on certain symmetric function.