Workings of the Deutsch-Jozsa Algorithm

Install and load the QuantumFramework paclet:

In[1]:=

PacletInstall["Wolfram/QuantumFramework"];Needs["Wolfram`QuantumFramework`"];

There are four possible Boolean functions with one input variable (

and

In[2]:=

Table[ResourceFunction["TruthTable"]@BooleanFunction[k,1],{k,0,3}]

Out[2]=



p	False
True	False
False	False

p	!p
True	False
False	True

p	p
True	True
False	False

p	True
True	True
False	True



Usually one of two quantum encodings are considered for these Boolean functions. The phase oracle encodes the output bit as a sign flip or a phase shift by an angle of π.

Show the corresponding circuits with their action on

|0〉

and

|1〉

In[3]:=

TableWith{qc=QuantumCircuitOperator[{"DeutschJozsaPhaseOracle",f}]},qc"Diagram",PlotLabelColumn[Style[#["Formula"]qc[#],8]&/@{QuantumState["0"],QuantumState["1"]},FrameAll],

,{f,4}

Out[3]=





Constant Boolean functions (

True

and

False

) correspond to either changing the overall global phase by π or doing nothing at all (empty circuit), whereas balanced functions (half

True

and half

False

) are encoded with

and

operators, which are just convenient names for Pauli

and

-Z

Another way of encoding these Boolean functions is to show more direct bit action with a Boolean oracle representation, which is using an auxiliary qubit initialized to

|0〉

to store its output.

Show all single Boolean oracles:

In[4]:=

TableWith{qc=QuantumCircuitOperator[{"DeutschJozsaBooleanOracle",f}]},qc"Diagram",

,{f,4}

Out[4]=





The Deutsch algorithm is then simply about measuring (in the X basis) the result of running such a quantum oracle on a uniform superposition as input (

|+〉

state):

In[5]:=

Table[QuantumCircuitOperator[{"+",QuantumCircuitOperator["DeutschJozsaPhaseOracle"[f]],QuantumMeasurementOperator["X"]}]["Diagram",ImageSizeSmall],{f,4}]

Out[5]=





The Boolean oracle version also requires phase shifting the initial output qubit by π, so that it is initialized as

|-〉

instead:

In[6]:=

Table[QuantumCircuitOperator[{"+","-"2,QuantumCircuitOperator["DeutschJozsaBooleanOracle"[f]],QuantumMeasurementOperator["X"]}]["Diagram",ImageSizeSmall],{f,4}]

Out[6]=





Or use built-in circuits with a random oracle as a default:

In[7]:=

QuantumCircuitOperator["DeutschPhase"]//TraditionalForm

Out[7]=

In[8]:=

QuantumCircuitOperator["Deutsch"]//TraditionalForm

Out[8]=

Then with certainty an outcome

|+〉/|



〉

means that an oracle is a constant function, while

|-〉/|



〉

means it's a balanced one:

In[9]:=

Table[Show[QuantumCircuitOperator[{"Deutsch",f}][]["ProbabilityPlot"],PlotLabelBooleanConvert[BooleanFunction[f-1,1]][x.],ImageSizeTiny],{f,4}]

Out[9]=





If one has more than one variable then the exact same procedure is called the Deutsch-Jozsa algorithm. For example for two variables, these are the corresponding phase and Boolean oracles:

In[10]:=

TableQuantumCircuitOperator[{"DeutschJozsaPhaseOracle",f,2}]"Diagram",

,{f,16}

Out[10]=





In[11]:=

TableQuantumCircuitOperator[{"DeutschJozsaBooleanOracle",f,2}]"Diagram",

,{f,16}

Out[11]=





With measurement now being done on two qubits:

In[12]:=

QuantumCircuitOperator[{"DeutschJozsaPhase",Automatic,2}]//TraditionalForm

Out[12]=

In[13]:=

QuantumCircuitOperator[{"DeutschJozsa",Automatic,2}]//TraditionalForm

There are not just constant and balanced functions now, but also unbalanced ones, about which the algorithm can't say anything at all, meaning outcome distribution is uniform for such cases:

Publisher Information

Contributed by: Wolfram Research, Quantum Computation Framework Team

Wolfram Language Example Repository

Workings of the Deutsch-Jozsa Algorithm

See Also

Publisher Information