I tried IBM’s Quantum Experience: I’m here to share the insights of this technology and give you the tools to do the same thing! As you read in my first article, Quantum Computing is faster than traditional computing. Here we will demonstrate it through Grover’s algorithm via Qiskit. So get ready and let’s dive in!
By Duccio Giovannelli
13 May 2021
The idea behind quantum computers is that their computation capability is exponentially faster against classical hardware. A quantum algorithm running on quantum computer benefits from the so-called quantum properties: superposition, entanglement, and interference.
The fact that Quantum Computing is faster than traditional computing can be demonstrated through Grover’s algorithm via Qiskit, an open-source framework for quantum development that provides tools for creating and manipulating quantum programs on IBM Quantum Experience (an online platform that allows public access to cloud-based IBM’s quantum computing services)
Demonstrating Grover’s algorithm with Qiskit
The second most famous quantum algorithm that demonstrates how a quantum computer outperforms a classical computer is Grover’s algorithm, which focuses on searching in an unordered list quadratically faster than the best classical algorithm. You can find the complete example here, but let’s try to recap its main concepts.
Suppose you have a list of N unsorted items and you have to look for the position of an element. With a classical algorithm, you’d have to check N/2 elements on average to find the element you are searching for, in the worst case -the element is the last- the whole list. This can be considered an O(N) complexity. With Grover's amplitude amplification it would be √n, a quadratic speedup!
Grover's implementation is a function where given an input it returns its negate if the input is the winner.
The Oracle function
note: |ω⟩ is the winning state (the index you are looking for in the list). |𝑥⟩ is the Dirac notation for a generic input qubit.
If we consider 2 qubits, so that we can represent 4 input states (00, 01, 10, 11), if we assume 11 to be the winning state, the oracle Uω returns -11.
The result of the oracle itself is not enough, we need to apply the reflection to amplify the probabilities of getting the winning state.
Here’s a geometric representation that helps understanding how it works:
Where: |s⟩ is the uniform superposition over all states
For a qubit and 2 states: 1/√2 |0⟩ + 1/√2 |1⟩
|ω⟩ and |s⟩ are not quite perpendicular because |ω⟩ occurs in the superposition with amplitude 1/√N
|s’⟩ = |s⟩ - |ω⟩ is perpendicular to |ω⟩
UₛUω |s⟩ (Grover’s diffuser) = 2 |s⟩⟨s| − I
The sum of oracle plus reflection is called Grover's iteration. To obtain the results the iteration is repeated O(√N) times.
How to test it in IBM’s Quantum Computer
To test Grover’s circuit on IBMQ, register here and get a token.
Here’s the code for 2 qubits:
Probability of the winning state is 0.949
Duccio is Extendi's mastermind for AI and Machine Learning. When he is not training algorithms you can find him diving on reefs, sailing, and taking beautiful pictures.
In this article, I will cover why building an ecommerce with the Jamstack architecture can benefit your business immensely and how, at Extendi, we rely on Commerce Layer’s headless commerce platform to do so.
What’s the key practice when it comes to delivering robust, secure, and easy-to-scale applications? Find out how your organization can benefit immensely from this approach in this article about Jamstack. At Extendi we have been using this architecture for delivering top-notch web applications, SaaS and websites.
At Extendi we are very passionate about technological advancements. Quantum Computing represents a new phase of the computing era, but what is it and how does it work? And most of all, why is it so important? In this article, I’ve tried to answer some of those questions in a simple way so everyone can get a peek into what the future will look like.