# Phase Oracle Gate

**Phase oracle** (or problem oracle) is an $n$-qubit gate that marks solutions to a computational problem by applying a phase (typically $-1$) to basis states satisfying a Boolean predicate $f: \{0,1\}^n \to \{0,1\}$. Phase oracles are fundamental to quantum search and optimization algorithms, encoding the problem structure into quantum interference.

## Definition

For a Boolean function $f(x)$ where $x \in \{0,1\}^n$, the phase oracle is:

$$O_f = \sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle\langle x|$$

or equivalently:

$$O_f |x\rangle = (-1)^{f(x)} |x\rangle$$

**Marking**:
- If $f(x) = 0$ (not a solution): apply identity, no phase change
- If $f(x) = 1$ (solution): apply $-1$ phase (or $Z$ gate eigenvalue -1)

## Phase Kickback Trick

When applied to a superposition of basis states, the phase oracle encodes the solution structure:

Starting with equal superposition: $|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x\rangle$

After oracle: $O_f |\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{f(x)} |x\rangle$

Solutions now have negative phase, enabling interference-based amplification via diffusion.

## Construction from Classical Function

**Direct implementation** (if function evaluation is efficient):

1. Evaluate function $f(x)$ classically on input $x$
2. Conditionally apply $Z$ gate (phase flip) based on $f(x)$
3. Inverse the function evaluation (reversible)

**Example (2-qubit OR gate oracle)**:
- Compute $f(x_1, x_2) = x_1 \lor x_2$ (mark states where at least one qubit is 1)
- Mark states $|01\rangle$, $|10\rangle$, $|11\rangle$ with phase $-1$

## Ancilla Qubits

For complex Boolean functions, ancilla qubits are often needed:

1. Initialize ancilla to $|0\rangle$
2. Compute $f(x)$ into ancilla (or last bit of ancilla)
3. If ancilla is $|1\rangle$, apply $Z$ gate
4. Uncompute $f(x)$ (reverse computation)

This preserves unitarity and reversibility. Ancilla can be reused across multiple oracle calls.

## Query Complexity

The oracle is treated as a **black box**: its cost is measured in terms of function evaluations (queries), not gate count.

- **Grover's search**: requires $O(\sqrt{N})$ oracle queries for $N = 2^n$ items
- **Hidden subgroup problem**: $O(\text{poly}(n))$ queries depending on subgroup structure
- **Optimization**: number of queries depends on solution density

## Applications in Quantum Algorithms

**Grover's search**:
- Mark database items matching a criterion
- Amplitude amplification via diffusion finds marked items in $O(\sqrt{N})$ queries

**Quantum optimization** (QAOA variant):
- Mark states with cost below threshold
- Iterate oracle + diffusion to concentrate probability mass

**Hidden subgroup problem**:
- Marked states are elements of a hidden subgroup
- Phase encoding enables efficient subgroup identification (Simon's algorithm, Shor's algorithm)

**Variational algorithms** (VQE, QAOA):
- Define problem Hamiltonian from constraint function
- Oracle encodes objective function as phase
- Hybrid classical-quantum loop finds solutions

## Problem-Specific Oracles

**Satisfiability (SAT)**:
- Mark satisfying assignments of Boolean formula
- Exponentially faster than classical exhaustive search (for large instances)

**Factoring** (Shor's algorithm):
- Mark states where order finding condition is met
- Oracle computes modular exponentiation and detects period

**Graph problems** (maximum cut, coloring):
- Mark valid colorings or cuts
- Quantum amplitude amplification finds solutions

## Designing Efficient Oracles

Efficient oracle design is critical for quantum advantage:

- **Circuit depth**: should be $O(\text{poly}(n))$ at worst
- **Gate count**: minimizes error accumulation
- **Reversibility**: uncompute ancillas to avoid decoherence
- **Parallelization**: reuse subcircuits for repeated function evaluation

## Relation to Other Gates

- [[quantum-gate-grover-diffusion|Grover diffusion]]: works in tandem with phase oracle in Grover's algorithm
- [[quantum-gate-controlled-unitary|Controlled-unitary gates]]: implement conditional operations for function evaluation in oracle circuits
- [[quantum-gate-qft|Quantum Fourier Transform]]: inverse QFT replaces diffusion in some variants (Fourier sampling)

## Limitations

- **No speedup without structure**: if solution density is very low ($O(1/2^n)$), oracle must be queried many times
- **Problem-dependent**: oracle design varies widely; no universal efficient oracle exists
- **Ancilla overhead**: complex functions require many ancilla qubits (reduces qubit efficiency)