//! # Deutsch-Jozsa Algorithm
//!
//! This algorithm was the first to show that quantum computers could have a speedup over classical computers.
//!
//! Consider a function $f(x)$ which takes an input of an $n$-bit string $x$ and returns 0 or 1.
//!
//! Suppose that $f(x)$ is either a **constant** function that has the same value $c \in \{0, 1\},  \forall x$, or a **balanced** function, where the value is 0 for half of the inputs, and 1 for the other half.
//!
//! The Deutsch-Jozsa problem is to find whether $f$ is *constant* or *balanced*, in as few function evaluations as possible.
//!
//! Using classical computing, in the worst case, this requires $2^{n-1}+1$ function evaluations.
//! Using quantum computing, this can be done with just one function evaluation.
//!
//! The function $f$, to be used in a quantum computer, must be specified specified by an oracle circuit $U_{f}$ such that $U_{f} \lvert x \rangle = (-1)^{f(x)}\lvert x \rangle$.
//!
//! ## The Algorithm
//!
//! 1. Initialize $n$ qubits in the state $\lvert 0, \dots, 0\rangle$.
//! 2. Apply the Hadamard gate $H$ to each qubit.
//! 3. Apply the oracle circuit $U_f$.
//! 4. Apply the Hadamard gate $H$ to each qubit.
//! 5. Measure each qubit. Let $y = (y_{1}, \dots, y_{n})$ be the list of measurement outcomes.
//!
//! From this procedure, we find that $f$ is constant if $y$ is the all zero string.

extern crate qcgpu;

use qcgpu::State;
use qcgpu::gates::h;

fn main() {
    // 3 qubits, f(x) = x_0 NOT x_1 x_2
    // Balanced
    let mut balanced_state = State::new(3, 1);

    balanced_state.apply_all(h());

    // Oracle U_f
    balanced_state.h(2);
    balanced_state.z(0);
    balanced_state.cx(1, 2);
    balanced_state.h(2);

    balanced_state.apply_all(h());

    println!(
        "{}",
        if balanced_state.measure() == 0 {
            "constant"
        } else {
            "balanced"
        }
    );

    // 3 qubits, f(x) = 0
    // Constant
    let mut constant_state = State::new(3, 1);

    constant_state.apply_all(h());

    // Oracle is equivilant to the identity gate, thus has no effect on the
    // state.

    constant_state.apply_all(h());

    println!(
        "{}",
        if constant_state.measure() == 0 {
            "constant"
        } else {
            "balanced"
        }
    );
}
