Quantum algorithms and approximating polynomials for composed functions with shared inputs
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
<jats:p>We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math> be an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi></mml:math>-bit Boolean function and consider an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>-bit function <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>F</mml:mi></mml:math> obtained by applying <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math> to conjunctions of possibly overlapping subsets of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> variables. If <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math> has quantum query complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Q</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>, we give an algorithm for evaluating <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>F</mml:mi></mml:math> using <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>O</mml:mi><mml:mo stretchy="false">~</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>Q</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>⋅</mml:mo><mml:mi>n</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:math> quantum queries. This improves on the bound of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>Q</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>⋅</mml:mo><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:math> that follows by treating each conjunction independently, and our bound is tight for worst-case choices of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math>. Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math>.By recursively applying our composition theorems, we obtain a nearly optimal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>O</mml:mi><mml:mo stretchy="false">~</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mi>d</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> upper bound on the quantum query complexity and approximate degree of linear-size depth-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math> AC<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi /><mml:mn>0</mml:mn></mml:msup></mml:math> circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi /><mml:mn>0</mml:mn></mml:msup></mml:math> circuits.As an additional consequence, we show that AC<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi /><mml:mn>0</mml:mn></mml:msup><mml:mo>∘</mml:mo><mml:mo>⊕</mml:mo></mml:math> circuits of depth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:math> require size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi mathvariant="normal">Ω</mml:mi><mml:mo stretchy="false">~</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mi>d</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mo>≥</mml:mo><mml:mi>ω</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mi>d</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> to compute the Inner Product function even on average. The previous best size lower bound was <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">Ω</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:msup><mml:mn>4</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> and only held in the worst case (Cheraghchi et al., JCSS 2018).</jats:p>