Promise problem
QuantumPromise problem: A decision problem where inputs are guaranteed to satisfy some condition. Many quantum speedups, including Deutsch-Jozsa, are proven on promise problems.
Promise problem: A decision problem where inputs are guaranteed to satisfy some condition. Many quantum speedups, including Deutsch-Jozsa, are proven on promise problems.