Deutsch-Jozsa Algorithm: How Quantum Computers Solve Problems in One Shot

You may have heard that Quantum computers solve problems incredibly fast as compared to Classical computers, utilizing the power of Quantum parallelism.

So, In this blog we will explore one of the first algorithms that practically demonstrated Quantum advantage and It was a foundational step to prove that Quantum computers can solve certain problems much faster than classical ones. We are Talking of Deutsch-Jozsa Algorithm.

Let’s Understanding problem to Solve

Suppose we have a magical washing machine, and you can put any cloth into that magical washing machine to wash. But when you take the cloth out, only two things can happen (only 2 cases are possible):

• Either All clothes become a red, round neck, M-size T-shirt. This machine is called a Constant washing machine.
• or Exactly Half of them are red and half are green. This one is called a Balanced washing machine.

To categorize which type of machine it is, a Normal person would have to check clothes one by one, and in the worst case they need to look at at least half of the clothes before and after washing. But suppose Harry Potter can tell the type of machine just by looking at one cloth. Here, Harry is the quantum computer, and the normal human is the classical computer.

Now, let’s come to the computer world. Consider a function f(x), also called an oracle function, that works like the washing machine.

The function takes an input x, which can be 0 or 1, and returns an output which is also 0 or 1.

Now this function is can to be only one of two types:

1. Constant function: No matter what input you give, the output is always the same.
   Examples:
   → f(0) = 0 and f(1) = 0 or
   → f(0) = 1 and f(1) = 1
2. Balanced function: The function returns 0 for half of the inputs and 1 for the other half.
   Examples:
   → f(0) = 0 and f(1) = 1
   → f(0) = 1 and f(1) = 0
   If you have 10 inputs in total, then a balanced function will output five 0s and five 1s.

And our task is simple, which is to find out whether the given function is constant or balanced.

How Classical computers attempt it

As we know, normal computers work with one bit at a time (either 0 or 1). So, in the worst case scenario, they have to check more than half of the possible inputs.

If you have checked only half and all outputs were the same, you still cannot be 100% sure, the function could still be balanced. You need to check one more input to be certain.

Suppose you have 10 entries and you start applying f(x):

A classical computer may need to check up to 6 inputs (half + 1) in the worst case before it can confidently say whether the function is constant or balanced.

1. f(0) → Start from here; check whether the output is 0 or 1
2. f(1) → Again check; see whether the output is 0 or 1
3. f(1) → Repeat
4. f(1) → Repeat
5. f(1) → Repeat
6. f(1) → To be sure, you have to calculate till here
7. f(1) → No need to check
8. f(1) → No need to check
9. f(1) → No need to check
10. f(1) → No need to check

This might look normal, but suppose for 10,000 entries you have to check 5,000 + 1 entries. Now observe the time complexity: in the worst case it is almost O(n/2), which increases linearly and becomes slow.

Hero in rescue: Quantum Computers

Now let’s see how quantum computers solve this problem with the Deutsch–Jozsa algorithm, improving compute speed and reduction in time complexity, and proving quantum advantage.

For solving this problem in a single shot, QPUs use quantum parallelism, which at its core happens with superposition and entanglement.

But just evaluating the function for all inputs is not enough. We also need a way to extract useful information. This is where interference comes in.

In short let me explain them:

• Superposition → A concept of quantum physics that enables multiple states of a single entity at once, like electrons. In quantum computing, it means that a qubit can have equal chances of being 0 and 1 at the same time, not just either of them.

We achieve superposition with the Hadamard gate in quantum computing.

• Entanglement → Again, a phenomenon in quantum physics where two or more qubits become linked in such a way that the state of one qubit instantly influences the state of the other, no matter how far apart they are.

In quantum computing, entanglement allows qubits to share information and correlate their outcomes, enabling complex computations that classical bits cannot perform efficiently. We create entanglement using gates like the CNOT gate in quantum circuits.

2 Entangled States (Distances don’t matter!)

• Interference → A fundamental principle in quantum mechanics where quantum states (wave functions) combine to either amplify or cancel out certain outcomes, similar to Sound and light waves.

In quantum computing, interference is used to boost the probability of correct answers and reduce the probability of wrong ones by carefully designing quantum gates and circuits.

This is achieved through constructive interference (where amplitudes add up) and destructive interference (where amplitudes cancel out), allowing the algorithm to proceed the computation toward the desired result in a single measurement.

Now let us discuss working of Deutsch–Jozsa algorithm:

1. Initialize the Qubits

• We Start with two qubits, which is simplest Version of Deutsch-Jozsa Algorithm:

Preparing Initial State

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

# Note that This Cirqmon shows ideal results and Qiskit code will inject some noise when Executed!

# 1. Create a Quantum Circuit with 2 qubit
qc = QuantumCircuit(2,2)
qc.x(1)

• First qubit (input qubit): Initialize to ∣0⟩ → But, its Already in ∣0⟩, so nothing to do.
  This will be the input that we will evaluate against the oracle function and we can have more than one input qubit.
• Second qubit (output qubit): Initialize to ∣1⟩ → By convention, qubits start in ∣0⟩, so we apply an X (NOT) gate to flip the state from ∣0⟩ to ∣1⟩.
  We also call this the ancillary qubit, and we flip it to take advantage of quantum interference, which will help us amplify the correct answers. We will have only one ancillary qubit, no matter how many input qubits there are.

So, now our Initial state becomes: |ψ₀⟩ = |0⟩ ⊗ |1⟩ = 01⟩

For n input qubits and 1 ancilla, this generalizes to:

|ψ₀⟩ = (|0⟩^⊗n) ⊗ |1⟩

That is, the first n qubits are each in |0⟩, and the ancilla qubit is in |1⟩.

2. Apply Hadamard Gates (Create Superposition)

Superposition

# 2. Apply hadamard to both Qubits

qc.h(0)
qc.h(1)

Now, to take quantum advantage, we apply a Hadamard gate (H) to both qubits.

• H|0⟩ → On applying Hadamard to the first qubit Q_0​, which was ∣0⟩ earlier, it now enters a superposition state:

→ H∣0⟩=∣0⟩ + ∣1⟩​ / √2

This is often called the ∣+⟩ state.

• H|1⟩ → On applying Hadamard to the second qubit Q_1, which was ∣1⟩earlier, it now enters a superposition state:

→ H∣1⟩=∣0⟩ - ∣1⟩​ / √2

This is often called the ∣-⟩ state.

State after Hadamard:
→ |ψ₁⟩ = (|0⟩ + |1⟩)/√2 ⊗ (|0⟩ − |1⟩)/√2

The input qubit is now in an equal superposition of ∣0⟩ and ∣1⟩, and the ancilla qubit is in a superposition with a relative minus sign (-), which will later help us use quantum interference to distinguish constant vs balanced functions and Amplify correct Calculations.

3. Apply the Oracle Function (Uf)

So basically, the oracle function is a special set of quantum gates that encodes the function f(x). (like inside dashed borders.)

Overall Deutsch Jozsa Algorithm Circuit

It performs the transformation, or you can call it a processing unit that gives a suitable output according to what kind of function this oracle box has encoded. We also call this a black box because we don’t know what is happening exactly at the quantum level to encode the function.
We only care about its input–output behavior, not its internal gate-level implementation.

Get Aditya Pal’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In more technical terms, It’s a unitary transformation:

Uf​ : ∣x⟩∣y⟩ ⟶ ∣x⟩∣ y⊕f(x) ⟩

Lets Understand this one but don’t be panicked if you don’t get it now, you can still conceptually understand what is Oracle function.

Now let’ s Break it down piece by piece:

• Uf is the oracle: a unitary (reversible) quantum gate that “knows” the function f(x).
• ∣x⟩ is the input register (your data qubits, e.g. ∣0⟩ or ∣1⟩ for 1-bit input).
• ∣y⟩ is the output/ancilla qubit (the helper qubit).
• f(x) is the classical function’s output (0 or 1).
• ⊕ means XOR Operation (like in simple Electronics it returns 0 if Inputs are same and 1 if they are different):

So the oracle does this:

It leaves the input ∣x⟩ unchanged, and updates the second qubit from ∣y⟩ to ∣y ⊕ f(x)⟩.

Or simply it says like - “ Take the current value of the second qubit (Ancilla) ∣y⟩, XOR it with the function’s output for that input |x⟩, and update the result in the Ancillary qubit.”

Now let’s Understand with Examples:

Take x as input and y as ancillary:

→ Ex-1: Constant function f(x)=0

• Transformation: ∣x⟩∣y⟩ → ∣x⟩∣ y⊕0 ⟩
• Here f(x) = 0 and ∣y⟩ = 1 which means 0 ⊕ 1 = 1 and since ∣y⟩ is already 1, So the oracle does nothing (identity).

→ Ex-2: Constant function f(x)=1

• Transformation: ∣x⟩∣y⟩ → ∣x⟩∣ y⊕1 ⟩
• Here f(x) = 1 and ∣y⟩ = 1 which means 1 ⊕ 1 = 0 but ∣y⟩ is 1,
  So it flips the second qubit to 0 state (like an X gate on the ancilla).

→ Ex-3: Balanced function f(x)=x (either 0 or 1)

For x = 0:

• ∣0⟩∣y⟩ → ∣0⟩∣ y⊕0 ⟩ = ∣0⟩∣y⟩
• So, it’s like f(x) = 0, ∣y⟩ = 1 meaning that 0 ⊕ 1 = 1.
  Here ∣y⟩ is already 1, So nothing changes on the second qubit. We do nothing.

For x = 1:

• ∣1⟩∣y⟩ → ∣1⟩∣ y⊕1 ⟩ = ∣1⟩∣ NOT(y) ⟩
• Here, it’s like Since f(x) = 1, ∣y⟩ = 1 and 1 ⊕ 1 = 0,
  So we need to flip the Ancillary Qubit, or like Applying X gate to Output qubit.

This behavior is exactly the same as a CNOT gate, where the first qubit is the control and the second qubit is the target.

We will try Balanced function, by Applying CNOT Gate (Example 3).

Oracle function

# 3. Apply CX Gate with Input (Q_1) as Control and (Q_2) as Target
# Its for simple Balanced Oracle function

qc.cx(0, 1)

4. Apply Hadamard Gates Again

Again Hadamard

# 4. Apply Hadamard again to Amplify correct calculation
qc.h(0)

Apply another Hadamard gate (H) to the input Qubits only.

This creates interference between the states, amplifying the correct answer.

State after second Hadamard:
|ψ₃⟩ (depends on whether f(x) is constant or balanced)

• If f(x) is constant, the amplitudes interfere constructively toward the
  ∣0⟩^⊗n state. ∣ψ3​⟩ has the input register in ∣0⟩⊗n (all zeros)
• If f(x) is balanced, the amplitudes interfere destructively for ∣0⟩^⊗n, so the state ends up in some non-zero pattern. ∣ψ3​⟩ has zero amplitude on
  ∣0⟩^⊗n and non-zero amplitude on other basis states

5. Measurement and results

# 5. Measure the qubit and store the result
qc.measure_all()

 # 6. Simulate the circuit
sampler = StatevectorSampler()
job = sampler.run([qc], shots=1024)
result = job.result()
pub_result = result[0]

print("Measurement Counts:", pub_result.data.meas.get_counts())

Now measure the first qubit. In this simulator, it shows results for all qubits including the ancilla, but to determine the kind of function, we only care about the input qubits.

For example, if here outcomes are |01⟩ and |11⟩, that means the first qubit is giving mixed results 0 and 1, while the second bit is just the ancilla.

• If the input qubit(s) measure |0⟩ (or all zeros for multiple inputs) → Function is Constant.
• If the input qubit(s) measure |1⟩ (or anything other than all zeros) → Function is Balanced.

So Here:

• |01⟩ → first qubit = 0
• |11⟩ → first qubit = 1

The first qubit is giving mixed results (both 0 and 1). So this Function is Balanced.

Full Code:

Code that you can Run on Qiskit’s noisy simulator.

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

# Note that This Cirqmon shows ideal results and Qiskit code will inject some noise when Executed!

# 1. Create a Quantum Circuit with 2 qubit
qc = QuantumCircuit(2)
qc.x(1)
qc.h(0)
qc.h(1)
qc.cx(0, 1)
qc.h(0)

# 3. Measure the qubit and store the result
qc.measure_all()

 # 4. Simulate the circuit
sampler = StatevectorSampler()
job = sampler.run([qc], shots=1024)
result = job.result()
pub_result = result[0]

print("Measurement Counts:", pub_result.data.meas.get_counts())

Final Thoughts

Now that you have understood one of the first proofs of quantum advantage through the Deutsch-Jozsa algorithm, you can try building it hands-on.

I have created a browser-based open source quantum simulator called Cirqmon, specially made for learners. It does not look complicated and needs no setup. You can just open it and start experimenting.

You can try it here: https://cirqmon.vercel.app/

Also, if you want to explore more blogs on quantum computing, feel free to check my other posts.