Scribd
Upload
10 views13 pages

Week - 4 - Quantum Boolean Oracles

The document introduces Boolean function oracles within the context of quantum computing, detailing concepts such as qubits, the Toffoli gate, and the transformation of classical gates into quantum oracles. It explains how oracles can represent various Boolean functions, including AND and XOR operations, and discusses their properties like linearity and quantum parallelism. Additionally, it highlights the significance of oracles in quantum computing, particularly in evaluating multiple instances of functions simultaneously.

Uploaded by

ramkumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views13 pages

Week - 4 - Quantum Boolean Oracles

The document introduces Boolean function oracles within the context of quantum computing, detailing concepts such as qubits, the Toffoli gate, and the transformation of classical gates into quantum oracles. It explains how oracles can represent various Boolean functions, including AND and XOR operations, and discusses their properties like linearity and quantum parallelism. Additionally, it highlights the significance of oracles in quantum computing, particularly in evaluating multiple instances of functions simultaneously.

Uploaded by

ramkumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

Boolean Function Oracles

Introduction to Quantum Computing

Jothishwaran C.A.

Department of Electronics and Communication Engineering


Indian Institute of Technology Roorkee

May 24, 2025


Outline
Qubits and Boolean strings
Multi-qubit Basis
n-qubit operations revisited

The Toffoli gate


Definitions
The circuit picture

From classical gates to oracles


The AND oracle
Single bit oracles

Defining Boolean Oracles


The XOR oracle
General Boolean Oracles

Oracles as Quantum gates


Some results
A different oracle
Boolean Strings as Basis Vectors

▶ A single-qubit computational basis vector can be represented as |x⟩,


where x ∈ {0, 1}.

▶ If there n such qubits, each with computational basis state |xi ⟩


where xi ∈ {0, 1} and i ∈ [0, n − 1].

▶ Computational basis vector for the n-qubit system can simply be


defined as |x0 ⟩ ⊗ |x1 ⟩ ⊗ · · · ⊗ |xn−2 ⟩ ⊗ |xn−1 ⟩. There are 2n such
vectors.

▶ Each of these basis vectors can now be represented as


n
|x0 x1 . . . xn−1 ⟩ ≡ |x⟩, where x ∈ {0, 1} .

▶ This notation shall be adopted for defining multi-qubit basis vectors


for all further discussions.
The Xn and Hn gates
▶ If the X gate is applied to each of the n qubits of the system. The
combined operator can be represented as:

X ⊗ X ⊗ · · · ⊗ X ≡ X ⊗n
| {z }
n-times
▶ When the H gate is applied to each of the n qubits of the system.
The combined operator can be represented as:

H ⊗ H ⊗ · · · ⊗ H ≡ H ⊗n
| {z }
n-times

▶ When these operators are applied to the n-qubit basis state |0n ⟩ the
results are as follows:

X ⊗n |0n ⟩ = |1n ⟩
1 X
H ⊗n |0n ⟩ = √ |x⟩
2n x∈{0,1} n
Toffoli gate: a formal introduction
▶ The Toffoli gate (CCX ) is a three qubit gate and has the following
actions on the three-qubit computational basis:

CCX |000⟩ = |000⟩ ; CCX |100⟩ = |100⟩


CCX |001⟩ = |001⟩ ; CCX |101⟩ = |101⟩
CCX |010⟩ = |010⟩ ; CCX |110⟩ = |111⟩
CCX |011⟩ = |011⟩ ; CCX |111⟩ = |110⟩

▶ The matrix form is given as:


 
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
 
0 0 1 0 0 0 0 0
 
0 0 0 1 0 0 0 0
CCX =  0

 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
 
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
The Toffoli Circuit

▶ Combining the circuit conventions defined previously and the


definitions of Boolean functions The circuit corresponding and the
actions to the Toffoli gate is:

|x0 ⟩ |x0 ⟩
|x1 ⟩ |x1 ⟩

|x2 ⟩ |(x2 + x0 · x1 )⟩

Figure 1: The Toffoli gate

▶ Here, each state |xi ⟩ is a computational basis vector for the


single-qubit state.
▶ Since there were no phase factors in the actions defined before, the
circuit also defines the resultant states for the input state vectors.
A particular setup

▶ Consider the Toffoli gate with a condition the target qubit is initially
fixed in the |0⟩ state:

|x0 ⟩ |x0 ⟩
|x1 ⟩ |x1 ⟩

|0⟩ |x0 · x1 ⟩

Figure 2: The Toffoli gate

▶ The effect of the Toffoli gate on these initial states can be


summarized as:

CCX |x0 ⟩ |x1 ⟩ |0⟩ = |x0 ⟩ |x1 ⟩ |x0 · x1 ⟩


The AND Oracle

▶ The CCX gate with the initial state as shown before transforms the
target qubit from |0⟩ to |x0 · x1 ⟩

▶ Therefore for any initial control state represented by by x0 x1 the


circuit transforms the input state into the output state
|x0 ⟩ |x1 ⟩ |x0 · x1 ⟩

▶ This circuit is referred to as the Quantum AND Oracle: The circuit


transforms an input state corresponding to the inputs of a classical
AND gate, with a target qubit set to |0⟩ into an output state where
the AND operation is performed and stored in the target qubit.

▶ The two-bit classical AND gate now has an equivalent three-qubit


quantum oracle.
Simpler Oracles
▶ If a two-bit classical gate has a three-qubit quantum oracle, then it
maybe possible to define a single bit classical gate with a two-qubit
oracle. Consider the following circuit:

|x⟩ |x⟩

|0⟩ |x⟩

Figure 3: A single bit oracle

▶ This is the equivalent oracle for the single bit function F (x) = x.
The other single bit oracle maybe defined as follows:

|x⟩ |x⟩ |x⟩ |x⟩ |x⟩ |x⟩

|0⟩ X |1⟩ |0⟩ X |x⟩


|0⟩ |0⟩

Figure 4: F (x) = 0 Figure 5: F (x) = 1 Figure 6: F (x) = x


Oracles with CNOT gates
▶ As discussed before, the CNOT gate acts on a two-qubit basis state
|x0 ⟩ |x1 ⟩ as shown below

CNOT |x0 ⟩ |x1 ⟩ = |x0 ⟩ |(x0 + x1 )⟩


▶ While this is equivalent to the XOR gate, it is not in the oracle form
like the case with the CCX gate.
▶ However, consider the following circuit:
|x0 ⟩ |x1 ⟩ |x0 ⟩

|x0 ⟩ |x0 ⟩
|x1 ⟩ |x1 ⟩

|0⟩ |(x0 + x1 ⟩)

Figure 7: The XOR oracle

▶ This circuit is the three-qubit oracle equivalent to the classical XOR


gate.
Oracles with CNOT gates
▶ A general n-bit classical Boolean function has an equivalent
(n + 1)-qubit quantum oracle representation UF that acts as follows.

UF |x⟩ |0⟩ = |x⟩ |F (x)⟩


n
here, x ∈ {0, 1} and |x⟩ is an element of the n-qubit computational
basis.
▶ The circuit representation of the same is as shown below. It should
be noted that the upper bundle of qubit wires represent the n-qubit
state.
|x⟩ UF |x⟩

|0⟩ |F (x)⟩

Figure 8: The general quantum Boolean oracle

▶ It is possible to build any Boolean oracle with the CNOT , CCX and
X gates.
Varying the inputs of the Oracles
▶ Since the oracle is a unitary transformation, they are transformations
since the inverse of UF is simply the adjoint, UF† .
▶ If the target qubit of an oracle is fixed to the |1⟩ state, then applying
the oracle UF on such a state yields the following:

UF |x⟩ |1⟩ = |x⟩ |1 + F (x)⟩


▶ The oracle is also, by its definition a linear transformation and so, if
we consider a state |x1 ⟩ + |x2 ⟩ (normalization is disregarded) where
n
x1 , x2 ∈ {0, 1} . Then, applying UF on this state gives:

UF (|x1 ⟩ + |x2 ⟩) |0⟩ = |x1 ⟩ |F (x1 )⟩ + |x2 ⟩ |F (x2 )⟩


note that the separable input state may not be separable after UF is
applied.
▶ This is ability of a quantum oracle to evaluate multiple instances of
the same function is a result of the linearity of the oracle. This
feature is famously know as Quantum Parallelism and it has no
classical equivalent.
Varying the inputs of the Oracles
▶ If the target state of the qubit is set to the |−⟩ state, the action of
UF yields the following:

1
UF |x⟩ |−⟩ = UF |x⟩ √ (|0⟩ − |1⟩)
2
1
= |x⟩ √ (|0 + F (x)⟩ − |1 + F (x)⟩)
2
▶ The resultant target qubit is in the state |−⟩ when F (x) = 0 and
− |−⟩ when F (x) = 1. The combined result can be written as,

UF |x⟩ |−⟩ = (−1)F (x) |x⟩ |−⟩


▶ In this case, it can be seen that the state of the target qubit is the
same but the output sate gains a phase that corresponds to the
value of F (x). This variation of the oracle is referred to as the
Phase Oracle implementation of the Boolean function.

You might also like