Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators

スポンサーリンク

概要

• 論文の詳細を見る

• We introduce a complexity measure r for the class $\mathcal{F}$ of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class $\mathcal{F}$, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in $\mathcal{F}$, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.

• （社）電子情報通信学会の論文
• 2010-02-01

著者

• FUKUHARA Hideaki

  Graduate School of Information Sciences, Tohoku University

• TAKIMOTO Eiji

  Department of Informatics, Kyushu University

• Takimoto Eiji

  Department Of Informatics Kyushu University

• Fukuhara Hideaki

  Graduate School Of Information Sciences Tohoku University

関連論文

• NPN-Representatives of a Set of Optimal Boolean Formulas
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
• NPN-Representatives of a Set of Optimal Boolean Formulas
• DS-1-2 On Formula Size Lower Bounds for Synthesis of Boolean Functions over Disjoint Sets of Variables
• Approximate Reduction from AUC Maximization to 1-norm Soft Margin Optimization (情報論的学習理論と機械学習)
• Adaptive Online Prediction Using Weighted Windows
• Approximate Reduction from AUC Maximization to 1-norm Soft Margin Optimization

スポンサーリンク