PaperlayerView exact revision on arXiv

Source-linked AI summary

Span-program-based quantum algorithm for evaluating formulas

Ben W. Reichardt, Robert Spalek

arXiv:0710.2630v3quant-ph

TL;DR

Classical evaluation of balanced ternary majority remains unresolved, and the natural randomized alpha-beta pruning generalization is suboptimal. The paper applies span-program and spectral analysis to adversary-balanced formulas over an expanded gate set, obtaining an optimal O(2d)-query algorithm for balanced ternary majority.

  • Problem

    Classical balanced ternary-majority evaluation is known only within bounds, and the natural randomized alpha-beta pruning generalization is suboptimal.

    Source: §1 · p. 2

  • Method

    The paper analyzes span programs through witness size and spectral properties, then applies the framework to adversary-balanced formulas.

    Source: §1 · p. 3, §4.1 · p. 11

  • Results

    O(2d) queries optimally evaluate balanced depth-d ternary-majority formulas on N = 3d inputs with bounded error.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The algorithm extends quantum formula evaluation to adversary-balanced read-once formulas over an expanded gate set, including arbitrary three-bit gates.

    Source: §1 · p. 1

    For highly unbalanced formulas with large depth, whether rebalancing can avoid substantially increasing the adversary lower bound remains unresolved.

    Source: §5.2 · p. 16

Abstract

from arXiv · show

We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. The main new tool is a correspondence between a classical linear-algebraic model of computation, "span programs," and weighted bipartite graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. In contrast, our algorithm generalizes the optimal quantum AND-OR formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.

1 Introduction

The paper extends optimal quantum formula evaluation beyond AND-OR formulas to adversary-balanced read-once formulas over a larger gate set. Its graph-based approach yields an optimal O(2d)-query algorithm for balanced ternary majority, whose classical complexity remains unresolved.

1 Introduction

  • The algorithm extends to adversary-balanced read-once formulas over gates including arbitrary three-bit gates, bounded fan-in EQUAL gates, and bounded-size AND, OR, NOT, and PARITY formulas.Adversary-balanced means the inputs to each gate have exactly equal adversary lower bounds.Source: §1 · p. 1
  • The method replaces each formula gate with a gadget in a weighted graph and uses spectral estimation to detect root-supported small-eigenvalue eigenvectors.The graph may also duplicate subformulas.Source: §1 · p. 1
  • Balanced depth-d ternary majority on N = 3d inputs has an optimal bounded-error quantum algorithm using O(2d) queries.The classical complexity is only known to lie between Ω((7/3)d) and O((2.6537 . . .)d), while randomized alpha-beta pruning takes expected O((8/3)d) time and is suboptimal.Source: §1 · pp. 1–2
  • The framework links span programs to weighted bipartite graphs, with evaluation represented by eigenvalue-zero eigenvectors.The paper develops witness size to analyze eigenvalue-zero and small-eigenvalue behavior.Source: §1 · p. 3
  • The paper's formula algorithm composes optimal gate span programs and analyzes the resulting graph spectrum before applying quantum-walk phase estimation.Its general result covers gate sets and formulas satisfying the stated adversary-balance condition.Source: §1 · p. 3

2 Span programs and eigenvalue-zero graph eigenvectors

A span program specifies a Boolean function through linear combinations of grouped input vectors. Its weighted bipartite graph represents true and false evaluations by zero-eigenvalue vectors on opposite output nodes, and graph gadgets compose these representations into formulas.

2 Span programs and eigenvalue-zero graph eigenvectors

  • A span program specifies a Boolean function by asking whether available grouped input vectors can linearly combine to the target vector.A grouped input is available only when all literals in its label are true.Source: §2 · p. 3

2.1 Span program as an adjacency matrix

  • The graph representation uses input and output edges of weight one, while other edge weights encode coordinates of the grouped input vectors.The grouped inputs connect through input edges; the output edge joins the distinguished output vertices.Source: §2.1 · p. 4, Figure 2 · p. 4

2.2 Eigenvalue-zero eigenvectors of the span program adjacency matrix

  • After deleting edges associated with true literals, a zero-eigenvalue solution supported on aO exists exactly when the function is true, and one supported on bO exists exactly when it is false.This is the graph's dual-rail encoding of the function.Source: §2.2 · p. 5

2.3 Dual span program

  • A NOT gadget uses two weight-one edges joined at a middle vertex to complement the graph's dual-rail encoding.A dual span program computes the negated function.Source: §2.3 · p. 5

2.4 Span program composition

  • Composition identifies a gate graph's input edges with subprogram output edges, inserting a NOT gadget for negated literals.Composing the gate programs according to a formula yields its composed graph and span program.Source: §2.4 · p. 6

3 Span program witness size

This section quantifies how span-program witness size controls the output support and eigenvalue behavior used to evaluate composed formulas. It also handles NOT gates separately from the general span-program analysis.

Subformula complexity

  • Subformula complexity tracks squared support at λ = 0, while at λ > 0 the subformula ratio is rescaled according to whether its literal is true or false.Literal inputs have complexity 1, and each subformula complexity is at least 1.Source: §3 · p. 7

Witness size

  • Witness size measures the minimum weighted squared length of a positive-input witness or the inverse squared length of a projected negative-input witness.For positive inputs the witness satisfies AΠ|w⟩ = |t⟩; for negative inputs it satisfies ⟨t|w′⟩ = 1 and ΠA†|w′⟩ = 0.Source: §3 · p. 8

Theorem 3.7

  • At λ = 0, a normalized eigenvalue-zero eigenvector has squared output support at least 1/wsize(P, x), while for small λ > 0 its output ratio separates true from false inputs.For true inputs the ratio is at most −1/(wsize(P, x)λ); for false inputs it is in (0, wsize(P, x)λ], up to small controlled terms.Source: §3 · p. 9

Proof of Theorem 3.7

  • The proof optimizes output support at λ = 0 and uses matrix inversion, the Woodbury formula, and Taylor expansions to control the small-nonzero-λ case.The lowest-order term corresponds to the witness-size definition, and higher-order terms are bounded.Source: §3 · p. 9

NOT gate

  • The general span-program analysis does not cover NOT gates, which are analyzed separately; their output complexity satisfies zO ≲ zi under the stated eigenvalue bound.The analysis assumes there are never two NOT gates in a row, so additive constants do not accumulate.Source: §3 · p. 9

4 Formula evaluation algorithm

The paper gives an O(Adv(ϕ))-query quantum algorithm for adversary-balanced formulas over an extended gate set. It builds gate span programs, analyzes their graph spectra, and applies phase estimation to evaluate the formula.

4.1 General formula evaluation result

  • Adversary-balanced means that every gate’s input subformulas have equal adversary bounds, and S includes arbitrary one-, two-, and three-bit gates.S also includes bounded-size {AND, OR, NOT, PARITY} formulas treated as single gates.Source: §4.1 · p. 10
  • The main algorithm evaluates adversary-balanced formulas over S using O(Adv(ϕ)) queries and running time Adv(ϕ)(log Adv(ϕ))^O(1) after input-independent classical preprocessing.The preprocessing requires O(1)-time coherent access to the preprocessed classical string.Source: §4.1 · p. 11
  • A balanced ternary majority formula of depth d is evaluable with O(2^d) quantum queries, which is optimal.Its adversary bound is 2^d, making this a corollary of the general formula-evaluation result.Source: §4.1 · p. 11

4.2 Optimal span programs for gates in S

  • For each gate in S, the paper constructs a span program with optimal witness size on inputs of equal complexity.Separate analyses are needed for EQUALk, MAJ3, and g because the general composition bound does not match their adversary lower bounds.Source: §4.2 · pp. 11, 13
  • For MAJ3, the span program has witness size 2, matching its adversary bound.For PARITY and OR composed over disjoint inputs, witness sizes combine as B + B′ and √(B^2 + B′^2), respectively.Source: §4.2 · pp. 11–12

4.3 Span program spectral analysis of ϕ

  • For a true formula input, the modified graph has a zero-eigenvalue eigenvector with constant support on the output vertex; for a false input, it has no output-supported eigenvector within ϵ/Adv(ϕ) of zero.The spectral gap and output support establish the soundness and completeness conditions used by the algorithm.Source: §4.3 · p. 13

4.4 Quantum algorithm

  • The quantum algorithm uses a graph quantum walk and phase estimation at precision O(1/Adv(ϕ)), with query complexity O(Adv(ϕ)).The walk’s spectrum and eigenvectors correspond to those of the weighted graph adjacency matrix.Source: §4.4 · p. 14

5 Extensions and open problems

The extensions explore which gates and balance conditions fit the span-program framework, alongside open questions about witness vectors, preprocessing, and larger span programs.

5 Extensions and open problems

  • The authors also ask whether the eigenvalue-zero eigenstate can provide witness information and point to further open problems.They identify these as possible extensions of Theorem 4.7.Source: §5 · p. 14

5.1 Four-bit gates

  • Thirty four-bit functions already belong to S, 25 more admit optimal span programs, and 20 others beat the square-root formula-size bound without matching the adversary lower bound.For other four-bit functions, understanding remains limited; the paper notes partial understanding for some threshold functions and suggests four-bit gates may already require more involved techniques.Source: §5.1 · p. 15

5.2 Unbalanced formulas

  • The analyzed unbalanced MAJ3 case has two equal input complexities; examples with one composed input can join S, but three differing complexities remain unresolved.For highly unbalanced formulas, rebalancing may also increase the adversary lower bound, an effect the authors say remains open.Source: §5.2 · pp. 15–16

5.3 Witness vectors and the adversary bound

  • When span-program witness size matches Adv, the witness-derived probability distributions are optimal for the minimax adversary formulation.The paper also notes that for many four-bit functions Adv± exceeds Adv, but it has no span program matching Adv± for functions where the bounds differ.Source: §5.3 · p. 16

5.4 Eliminating the preprocessing

  • For many formulas, preprocessing can be eliminated by computing each gate's decomposition separately and combining them at runtime.The combination works because gate input/output edge weights are all one; unbalanced NAND trees can instead have subformula-dependent input-edge weights.Source: §5.4 · p. 16

5.5 Arbitrary {AND, OR, NOT, PARITY} formulas

  • The proof also works when each inner h_i has equal-adversary-bound inputs and the bounds across h_i gates differ by at most a constant factor.The authors believe the O(1)-size restriction on the outer AND/OR/NOT/PARITY formula g may be weakened, but leave that analysis aside.Source: §5.5 · p. 17

5.6 New algorithms based on span programs

  • The paper composes only bounded-size span programs for functions on O(1) bits; whether asymptotically large span programs yield useful quantum algorithms remains open.Candidate problems are noted, and the framework applies to span programs over C, not only monotone ones.Source: §5.6 · p. 17

A Proof of Theorem 3.7

The appendix establishes equivalent formulations of span-program witness size and develops matrix estimates used in the proof of Theorem 3.7.

A Proof of Theorem 3.7

  • The two expressions defining wsize(P, x) are equivalent, so witness size is well defined.The proof uses pseudoinverse and projection identities; Figure 6 summarizes the matrices used in this section.Source: A Proof of Theorem 3.7 · pp. 19–20, Figure 6 · p. 21
  • For any fixed span program, the witness sizes of P and its dual P† differ by O(1), despite their different expressions for true and false inputs.The dual computes the negation of the original span program's function.Source: A Proof of Theorem 3.7 · p. 20
  • The appendix relates a rough upper bound on the exact expressions derived later to wsize(P, x).It establishes ˜z′(P, x) ≲ wsize(P, x).Source: A Proof of Theorem 3.7 · p. 20
  • Witness size is monotone increasing in each input complexity z_i.Source: A Proof of Theorem 3.7 · p. 20

A.1 Quantitative eigenvalue-zero spectral analysis of AGP

This subsection quantifies the eigenvalue-zero characterization by relating normalized output-node overlap in the graph to span-program witness size.

A.1 Quantitative eigenvalue-zero spectral analysis of AGP

  • The graph GP(x) is formed by deleting edges whose input literals evaluate to true; the resulting zero-eigenvector equations characterize the output.The proof uses grouped inputs, treating their vertices and weights together.Source: §A.1 · pp. 21–22
  • A normalized eigenvalue-zero eigenvector can have nonzero output-node amplitude at a_O exactly when fP(x)=1, and at b_O exactly when fP(x)=0.The theorem gives quantitative lower bounds on the squared overlap in terms of witness size and input complexities.Source: §A.1 · pp. 21–22

A.2 Small-eigenvalue spectral analysis of AGP

This subsection analyzes small eigenvalues by tracking input ratios and expanding the output ratio around λ=0, yielding bounds in terms of witness size.

A.2 Small-eigenvalue spectral analysis of AGP

  • For sufficiently small λ relative to each input complexity z_i, the grouped input ratios exist and their associated ˜s_j values are bounded by the grouped complexities ˜z_j.The result assumes 0 < λ ≤ ϵ/z_i for every input.Source: §A.2 · p. 23
  • The analysis expands the output ratio rO in λ and bounds its transformed value sO by the span-program witness size.The proof uses grouped input complexities and compares ˜z with ˜s through Lemma A.6.Source: §A.2 · pp. 24, 27
  • The matrix inverse needed in the ratio analysis exists when λ is sufficiently small relative to all z_i.The stated condition is 0 < λ ≤ ϵ/z_i for every input.Source: §A.2 · pp. 24–25
  • A block decomposition and Schur-complement argument support the expansion, with V differing from its leading matrix bV by O(λ^2∥˜s∥^2).Source: §A.2 · pp. 24–26

B Quantum algorithm

The section motivates replacing a nearly optimal continuous-time walk approach with a discrete-time quantum walk to avoid query overhead.

B Quantum algorithm

  • The direct phase-estimation approach is nearly optimal, but simulating continuous-time quantum dynamics with discrete oracle queries adds overhead.The section presents this approach as optional motivation before the discrete-time construction.Source: B Quantum algorithm · p. 27
  • The authors use a discrete-time quantum walk in the proof to avoid the continuous-time simulation overhead.Source: B Quantum algorithm · p. 27
  • The continuous-time approach is optional motivation, and readers may skip directly to Section B.2.Source: B Quantum algorithm · p. 27

B.1 Intuition: Continuous-time quantum walk algorithm

The section describes a continuous-time algorithm that uses phase estimation on a weighted graph adjacency matrix to test formula evaluation. Its query cost is nearly optimal, but implementing the graph evolution incurs a super-constant overhead.

B.1 Intuition: Continuous-time quantum walk algorithm

  • ALG′ prepares the output-node state and uses phase estimation on the graph adjacency operator, accepting when the measured eigenvalue is zero.The operator is normalized by a norm independent of the input to minimize input dependence.Source: §B.1 · p. 28
  • True inputs yield a zero-eigenvalue state with constant output-node support, giving constant acceptance probability; false inputs have no supported near-zero eigenstate.Completeness follows from the support bound, while soundness follows from the spectral gap and bounded phase-estimation error.Source: §B.1 · p. 28
  • Phase estimation needs O(Adv(ϕ)) calls to the evolution operator, but implementing that operator requires input-oracle queries because the graph depends on x.Only input edges depend on x; their exponential uses two oracle queries, while the other-edge term uses none, and a Lie product decomposition approximates the combined evolution.Source: §B.1 · p. 28
  • Higher-order Lie product formulas reduce the implementation overhead to N^o(1), which remains super-constant and prevents this approach from yielding an optimal query bound.The best stated bound for this approach is O(Adv(ϕ)) · N^o(1) queries.Source: §B.1 · p. 28

B.2 Proof of Theorem 4.7: Discrete-time quantum walk algorithm

The proof avoids continuous-time simulation overhead by constructing a discrete-time coined walk whose spectrum and eigenvectors correspond to those of the weighted graph adjacency matrix.

B.2 Proof of Theorem 4.7: Discrete-time quantum walk algorithm

  • The construction uses a discrete-time, or “coined,” quantum walk Ux whose spectrum and eigenvectors correspond to those of the graph adjacency matrix.Source: §B.2 · p. 28
  • The algorithm runs phase estimation on Ux to evaluate the formula.Source: §B.2 · p. 28
  • Each call to Ux uses exactly one oracle query, avoiding the query overhead of continuous-time simulation.Source: §B.2 · p. 28

B.2.1 Construction of the coined quantum walk Ux

The construction factors the weighted graph matrix into a form that supports a coined quantum walk, then relates the walk's spectrum to formula truth. Input-dependent oracle phases modify only input edges, while the walk preserves the output-edge signal needed for phase estimation.

B.2.1 Construction of the coined quantum walk Ux

  • The construction factors the weighted adjacency matrix as a constant times Δ†◦Δ, with Δ having unit row norms, then applies Szegedy’s correspondence theorem [Sze04].The walk is built from a reflection and a swap; the cited theorem relates its spectrum to that of the associated matrix.Source: §B.2.1 · p. 29
  • Because the adjacency matrix may have complex entries, the factorization adjusts their phases, unlike the real-symmetric NAND construction [CRˇSZ07].The walk is a coined quantum walk: a swap followed by reflection about the span of the constructed states.Source: §B.2.1 · p. 29
  • The coined walk's eigenvalues and eigenvectors correspond to those of the associated Hermitian matrix, with walk eigenvalues determined by the matrix eigenvalues.Source: §B.2.1 · p. 29
  • Input-dependent oracle phases alter the rows for input vertices, zeroing the corresponding matrix entries when xi = 1 while leaving other entries unchanged.Source: §B.2.1 · p. 30
  • For a true formula, Ux has eigenvalue ±1 eigenstates with Ω(1) support on the output edge |aO, bO⟩.These walk eigenstates arise from the graph's eigenvalue-zero state with output-vertex support.Source: §B.2.1 · p. 30
  • For a false formula, Ux has no eigenstates supported on the output edge with eigenvalues ±eiλ for the stated small-λ range.Source: §B.2.1 · p. 30

B.2.2 Algorithm ALG, correctness, and query and time complexity

ALG decides a formula’s value by phase-estimating an input-dependent walk from the output edge. Its correctness follows from a completeness–soundness gap, and its query complexity is O(Adv(ϕ)).

Algorithm ALG

  • ALG starts on the output edge, runs phase estimation on Ux, and outputs true for measured phase 0 or π, otherwise false.The algorithm takes x as input and returns true or false.Source: §B.2.2 · p. 30

Correctness

  • For ϕ(x)=1, U(x) has eigenstates with eigenvalue ±1 and Ω(1) squared support on the output edge, giving Ω(1) completeness for sufficiently small constant error.For ϕ(x)=0, phase estimation returns 0 or π only if an error occurs, so soundness can be kept below completeness; the resulting constant gap can be amplified.Source: §B.2.2 · pp. 30–31

Query and time complexity

  • ALG makes O(Adv(ϕ)) queries to the input oracle.The stated time-efficiency argument allows polynomial-time preprocessing depending on ϕ but not x, including preparation of coin-diffusion operators.Source: §B.2.2 · p. 31

C Table of functions on up to four bits

The appendix catalogs four-bit Boolean functions up to input permutations and input/output complementation, recording known adversary bounds and span-program results. Its examples include partly unbalanced gate costs and matching span programs for a range of functions.

C Table of functions on up to four bits

  • The table organizes 222 inequivalent functions by input count and, for four-input functions, polynomial degree and adversary bounds; checkmarks mark known optimal span programs.Equivalence permits input permutations, complementation of a subset of input bits, and output complementation; the table also reports formula size and selected comments.Source: C Table of functions on up to four bits · pp. 31–32

C.1 Function #831, MAJ3, with partly unbalanced inputs:

  • For MAJ3 with first two input costs 1 and third cost β, an optimal span program with equal first two input complexities also settles the complexities of functions #287 and #1647.Source: §C.1 · p. 38

C.2 Function #975 with partly unbalanced inputs:

  • For #975 with costs (1,1,β), the adversary bound is β + 1, and a span program with matching witness size is given.The text relates this cost pattern to evaluating x3 first, then one of x1 or x2; it also settles #495 and #1695.Source: §C.2 · p. 38

C.3 Function #960, EQUAL3, with partly unbalanced inputs:

  • The partly unbalanced EQUAL3 analysis also settles the complexities of #424 and #1680.The passage identifies the related functions as EQUAL3(x1, x2, x3 ∧ x4) and EQUAL3(x1, x2, x3 ⊕ x4).Source: §C.3 · pp. 38–39

C.4 Function #963 with partly unbalanced inputs:

  • For #963, the partly unbalanced case gives a matching span program and settles the complexities of #2032, #426, and #1776.The two symmetrical inputs have cost 1 and the third has cost β.Source: §C.4 · p. 39

C.5 Function #828, EXACT2 of 3, with partly unbalanced inputs:

  • For #828, EXACT2 of 3, a partly unbalanced adversary analysis also settles #1912, #286, and #1641.The costs considered are (1,1,β).Source: §C.5 · p. 39

C.6–C.9

  • For functions #393, #989, #1968, and #1910, the cited passages each state that an optimal adversary matrix and a matching span program are provided for the function.Source: §C.6 · p. 40, §C.7 · p. 40, §C.8 · p. 40

C.10–C.12

  • For #317, a matching span program follows by composing the AND3 and MAJ3 span programs; the appendix also gives optimal adversary matrices and matching span programs for #5790 and #385.Source: §C.10 · p. 40, §C.11 · p. 41, §C.12 · p. 41
Loading 0710.2630v3…