In a quantum algorithm for this task, each iteration rotates the state in a two-dimensional subspace. For 10 points each:
[10e] Name this task performed in “O of root n” query complexity by Grover’s algorithm. A classical algorithm that explores branches of a tree as far as possible before backtracking is named for performing this task “depth-first.”
ANSWER: search [accept quantum search; accept depth-first search; prompt on DFS]
[10h] Grover’s algorithm begins by preparing a uniform superposition state, which can be created by applying this quantum gate to each of n “zero” qubits. This quantum gate maps “zero” to “plus” and “one” to “minus.”
ANSWER: Hadamard gate [or Walsh–Hadamard gate; prompt on H]
[10m] The Hadamard and CNOT gates can be used to prepare maximally entangled two-qubit quantum states named for this physicist, whose namesake theorem shows any local hidden-variable theory violates certain inequalities.
ANSWER: John Stewart Bell [accept Bell’s theorem or Bell states]
<Editors, Other Science>