QML — Quantum Oracle
Quantum Oracle is a black box used extensively in quantum algorithms for the estimation of functions using qubits. Estimation in a classical computer is set up with an n-dimensional input x producing an m-dimensional output f(x)
The n-dimensional vector x is encoded as quantum information by considering n qubits each storing a single bit of information as below
Quantum oracles help transform a system from a quantum state |x⟩ into a state |f(x)⟩, through the evolution of quantum states.
Recap
In order to fully appreciate this article a basic understanding of linear algebra and quantum physics good to have. This is the second article of my series Quantum Machine Learning (QML), refer to my previous post on Qubits and a mathematical article on Hilbert Space.
I would also suggest going over the excellent set of articles by Jonathan Hui in his Quantum Computing series. Having a basic knowledge of quantum gates and two-qubit operators are also required for understanding this blog.
Before jumping into the details of the oracle, let us revisit some of the properties of the unitary time evolution of a quantum state.
Quantum State Evolution
In quantum mechanics, the total probability of a system remains constant as its state evolves through time. This puts constraints on any operator acting on a quantum system in a given state, let us see how
Operator U(t’) is applied on the system at time t
Therefore the two constraints for state evolution are
- The operator matrix should be unitary, ||U||=1
- The input and output dimension of the system states are equal
Formulating the oracle
We define an operator O as the oracle and try the following
This equation is not feasible, it violates the second constraint mentioned above where the input (n) and output dimension (m) are not the same
For an invertible function, the unitary operator property doesn’t hold true, thereby violating the first constraint mentioned above.
To solve the above issue, we introduce an additional second register (y) to store the output. The formulation is shown below
Measurement happens on the output of the second qubit |y⟩, as y is known then f(x) can be easily computed. Like other quantum operators, O is also linear in nature and is applicable to any generic system state
Application of the oracle operator (O) on this yields
Phase Oracle
There still exists a formulation of the oracle where there is no need for the introduction of an extra qubit. The Oracle acts by introducing a global phase on the input qubit shown here
If the input qubit state|x⟩ is a computational basis state, then it becomes a global phase and is not observable. But this oracle works very well if it is applied on a superposition of basis states in a controlled manner.
Both the oracle formulation is used in different setups of quantum algorithms. Choosing among the oracle setup heavily depends upon the nature of the quantum algorithm at play.
Next Steps
To fully appreciate the working of a quantum oracle it is necessary to showcase its application in a quantum algorithm. In the next article, we would go over a simple quantum algorithm.
