Quantum Algorithms for Connectivity and Related Problems

Understand

An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems.

• The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input.
• Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size.
• We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph.