Span-program-based quantum algorithm for the rank problem

Understand

Recently, span programs have been shown to be equivalent to quantum query algorithms.

• It is an open problem whether this equivalence can be utilized in order to come up with new quantum algorithms.
• We address this problem by providing span programs for some linear algebra problems.
• We develop a notion of a high level span program, that abstracts from loading input vectors into a span program.