Create Oracle

As a first step to creating the oracle, create a helper circuit called xorGate. This circuit reads qubits 1 and 2, and flips qubit 3 from $$|0\rangle$$ to $$|1\rangle$$ if qubits 1 and 2 have different values.

xorInnerGates = [cxGate(1,3);
                 cxGate(2,3)];
xorGate = quantumCircuit(xorInnerGates,Name="XOR");

Next, loop through all edges in the graph and write the value of xorGate applied to the startNode and endNode qubits into a new helper qubit representing the edge. This increases the number of qubits from 4 to 8 because there are four edges. The first four qubits represent the bit string to evaluate, while the other qubits begin in state $$|0\rangle$$ before xorGate is applied.

[startNodes,endNodes] = findedge(g);
N = numnodes(g);
E = numedges(g);
gates = [];
for k = 1:E
  gates = [gates; 
           compositeGate(xorGate,[startNodes(k),endNodes(k),N+k])];
end

Next, the oracle must verify that the helper qubits representing the edges are in state $$|1\rangle$$, since xorGate returns $$|1\rangle$$ when the two nodes connected by the edge have different states. This verification requires the addition of a ninth qubit that has a state of $$|1\rangle$$ when the coloring is valid, and $$|0\rangle$$ otherwise. Use the mcxGate function to determine the value of this final qubit, and create a circuit for the oracle.

lastQubit = N+E+1;
gates = [gates; 
         mcxGate(N+(1:E),lastQubit,[])];
oracle = quantumCircuit(gates,lastQubit);
oracle.Name = "Oracle"

oracle = 

  quantumCircuit with properties:

    NumQubits: 9
        Gates: [5×1 quantum.gate.CompositeGate]
         Name: "Oracle"

Plot the circuit representing the oracle to view all of the qubits and gates. Use the QubitBlocks option to draw red lines between the different groups of qubits: the first four qubits at the top of the circuit diagram represent the node colors being checked, the next four qubits are the helper qubits to check the nodes connected by each edge, and the final qubit at the bottom determines whether the graph coloring is valid.

plot(oracle,QubitBlocks=[4 4 1])

Check Initial Oracle Behavior

Construct two input configurations, one valid (1001) and one invalid (1111), and apply the oracle circuit to each of them to check its behavior. The input configuration is encoded in the left-most four characters of each bit string, and the value of interest is the last qubit (the right-most character) in the output bit string.

Start with the invalid coloring 1111, where all nodes are the same color.

invalidColors = "111100000";
inputState1 = quantum.gate.QuantumState(invalidColors);
formula(inputState1)

ans = 

    "1 * |111100000>"

outputState1 = simulate(oracle,inputState1);
formula(outputState1)

ans = 

    "1 * |111100000>"

The last qubit of the simulated state is 0, so the oracle correctly determines that not all of the nodes can be the same color. Next, check the coloring 1001.

validColors = "100100000";
inputState2 = quantum.gate.QuantumState(validColors);
formula(inputState2)

ans = 

    "1 * |100100000>"

outputState2 = simulate(oracle, inputState2); 
formula(outputState2)

ans = 

    "1 * |100111111>"

In this case, the last qubit is 1, so 1001 is a valid graph coloring, where each edge connects nodes of different colors. This check confirms that the behavior of the oracle is correct for these two cases.

Refine Oracle into State Oracle

The oracle currently works correctly, but it alters the input bits during execution. A requirement of Grover's algorithm is that the oracle must be a state oracle. That is, after the oracle is applied to a standard state, the bit values must be the same as the input state with only the phase changing. A valid bit string (indicating a valid coloring of the graph) should have a phase of -1 after the oracle operates, while an invalid bit string should have an unchanged phase of 1 after the oracle operates. Achieving this behavior requires additional modifications to the oracle.

Start by adding gates that revert all the helper qubits for the edges to $$|0\rangle$$ by flipping any values that were previously flipped.

oracle.Gates = [oracle.Gates; 
                flip(oracle.Gates(1:end-1))];

Next, note how state $$|-\rangle =\left(|0\rangle -|1\rangle \right)/\sqrt{2}$$ interacts with the X gate. Applying the X gate, which flips between the states $$|0\rangle$$ and $$|1\rangle$$, flips the phase of the $$|-\rangle$$ state: $$X|-\rangle =X\left(|0\rangle -|1\rangle \right)/\sqrt{2}=\left(|1\rangle -|0\rangle \right)/\sqrt{2}=-|-\rangle$$. This behavior is ideal for the last qubit in the oracle. So, passing that qubit into the oracle in state $$|-\rangle$$ ensures that the output bit string is the same as the input, while indicating valid graph colorings with an altered phase of -1.

Plot the final circuit for the state oracle.

plot(oracle)

Check Final State Oracle Behavior

To check the behavior of the state oracle, use the same two input bit strings as before. Start with the invalid graph coloring 1111, where all nodes are the same color.

invalidColors = "11110000-";
inputState1 = quantum.gate.QuantumState(invalidColors);
formula(inputState1)

ans = 

    "1 * |11110000->"

outputState1 = simulate(oracle,inputState1); 
formula(outputState1)

ans = 

    "1 * |11110000->"

The oracle correctly determines that the graph coloring is not valid. The phase of the output bits is unchanged. Next, check the coloring 1001.

validColors = "10010000-";
inputState2 = quantum.gate.QuantumState(validColors);
formula(inputState2)

ans = 

    "1 * |10010000->"

outputState2 = simulate(oracle,inputState2);
formula(outputState2)

ans = 

    "(-1-3.8858e-16i) * |10010000->"

In this case, the state oracle correctly flips the phase to -1 because the graph coloring is valid. The small nonzero imaginary part is due to floating-point round-off error.

State Oracle Code

This function creates a state oracle circuit for a specified input graph.

function oracle = oracleGraphColoring(g)

xorInnerGates = [cxGate(1,3);
                 cxGate(2,3)];
xorGate = quantumCircuit(xorInnerGates,Name="XOR");

[startNodes,endNodes] = findedge(g);
N = numnodes(g);
E = numedges(g);

gates = [];
for k = 1:E
  gates = [gates; 
           compositeGate(xorGate,[startNodes(k),endNodes(k),N+k])];
end

lastQubit = N+E+1;
gates = [gates; mcxGate(N+(1:E),lastQubit,[])];
oracle = quantumCircuit(gates,lastQubit);
oracle.Name = "Oracle"

oracle.Gates = [oracle.Gates; 
                flip(oracle.Gates(1:end-1))];

end

Diffuser Code

This function creates a diffuser circuit with a specified number of nodes. Save this function in a file on the MATLAB path.

function cg = diffuser(n)
gates = [hGate(1:n);
         xGate(1:n);
         hGate(n);
         mcxGate(1:n-1, n, []);
         hGate(n);
         xGate(1:n);
         hGate(1:n)];
cg = quantumCircuit(gates,Name="Diffuser");
end

Check Diffuser Behavior

Create a diffuser circuit for the four-node graph coloring problem and plot the circuit.

diffuserG = diffuser(N);
plot(diffuserG)

Verify that the diffuser applies a reflection of $$I_N-2|e\rangle \langle e|$$ by comparing the circuit matrix of diffuserG with a manually constructed reflection matrix.

e = ones(2^N,1);
e = e/norm(e);
M = eye(2^N) - 2*(e*e');
norm(getMatrix(diffuserG) - M)

ans =

   1.2243e-15

The result is zero (up to round-off error), which confirms that the diffuser circuit applies the expected reflection.