A (simple) classical algorithm for estimating Betti numbers
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 describe a simple algorithm for estimating the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-th normalized Betti number of a simplicial complex over <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> elements using the path integral Monte Carlo method. For a general simplicial complex, the running time of our algorithm is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>O</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mn>1</mml:mn><mml:msqrt><mml:mi>γ</mml:mi></mml:msqrt></mml:mfrac><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mi>ε</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:msup></mml:math> with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>γ</mml:mi></mml:math> measuring the spectral gap of the combinatorial Laplacian and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ε</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math> the additive precision. In the case of a clique complex, the running time of our algorithm improves to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo movablelimits="true" form="prefix">max</mml:mo></mml:mrow></mml:msub></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>O</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mn>1</mml:mn><mml:msqrt><mml:mi>γ</mml:mi></mml:msqrt></mml:mfrac><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mi>ε</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:msup></mml:math> with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>λ</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo movablelimits="true" form="prefix">max</mml:mo></mml:mrow></mml:msub><mml:mo>≥</mml:mo><mml:mi>k</mml:mi></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>λ</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo movablelimits="true" form="prefix">max</mml:mo></mml:mrow></mml:msub></mml:math> is the maximum eigenvalue of the combinatorial Laplacian. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers. On clique complexes it matches their running time when, for example, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>γ</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="normal">Ω</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="normal">Ω</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>.</jats:p>