30 votes

Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: ...
Craig Gidney's user avatar
  • 1,518
4 votes

Property testing in other metrics?

The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations ...
Clement C.'s user avatar
  • 4,461
3 votes

Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set. Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then ...
Tim's user avatar
  • 627
1 vote

Oracle Construction for Grover's Algorithm

You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas ...
Daniel Hauck's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible