Two problems have appeared earlier: the decision version of factoring ('does have a…
PHYSICS · Subjective · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch What quantum computers can compute efficiently
Problem
Two problems have appeared earlier: the decision version of factoring ('does N have a factor at least 2 and less than k?'), solved by order finding, and unstructured search for a marked item among N candidates given only oracle access to a marking function, solved by Grover's algorithm. For each problem, name the complexity classes it is known to belong to, and state whether each placement is proved outright, true only relative to a black-box oracle, or believed but unproved.