◐Attested & literatureQuantum query algorithm
Given oracle access to a weighted graph on N vertices of maximum degree d whose edge weights are conductances, so that an edge of weight w carries resistance 1/w, estimate the effective resistance between a chosen pair of vertices s and t to within a factor of 1 + ε. Wang poses it as ENA-ER: for a network with |V| = N, deg(G) ≤ d, edge conductances normalized to 1 ≤ w_e ≤ c for every edge — equivalently edge resistances in [1/c, 1] — and spectral gap λ2(L_G) ≥ λ > 0, estimate R_eff(s, t) up to multiplicative error ε, succeeding with probability at least 2/3, given a procedure Pv that on input a vertex index and a number k returns the k-th edge incident to that vertex and a procedure Pe that on input an edge index returns that edge's two endpoints and its weight, both of which Wang assumes can be implemented in time poly(log(N)).
◐Attested & literatureQuantum walk
Given oracle access to N items carrying no promise about the underlying function, find two items that are equal, or establish that all N are distinct.
◐Attested & literatureQuantum query algorithm
We are given an undirected graph G on n vertices, known explicitly in advance, together with oracle access to a labeling of the vertices by 1 and 0; the graph collision problem is to decide, by querying that labeling, whether there exist a pair of vertices, connected by an edge, both of which are labeled 1. Only the labeling is queried and never the graph, which is why Magniez, Santha and Szegedy can restate the task as deciding whether the set of vertices of value 1 forms an independent set in G. It is not either of the two problems it is easily confused with: collision finding asks for two arguments of a two-to-one function that share a value, and element distinctness drops that promise and asks whether any two of N items are equal. Those two share a single other Zoo entry, Collision Finding and Element Distinctness, and a single record here, element-distinctness; neither of them has a graph or an edge relation in it.
◐Attested & literatureQuantum query algorithm
Given oracle access to k matrices of size n × n, where a query names a matrix index x together with a pair of indices i, j and returns the ij entry of the x-th matrix, decide whether all k of the matrices commute with one another.
◐Attested & literatureQuantum query algorithm
Given three n×n matrices A, B and C over a field, decide whether AB = C, rather than computing the product and comparing it entry by entry.
◐Attested & literatureQuantum query algorithm
Determine the value at the root of a read-once Boolean formula, canonically a NAND tree on N variables, given only oracle access to the variables and using as few queries as possible.
◐Attested & literatureQuantum walk
Given oracle access to a graph built by joining two depth-n binary trees with a random weld, so that every node except the two roots has degree three, start from the label of one root and find the label of the other root.