Toward Solving Optimization Problems With A Quantum Computer | by Frank Zickert | Quantum Machine Learning | Aug, 2022
Practical Quantum Machine Learning
Do you want to get started with Quantum Machine Learning? Have a look at Hands-On Quantum Machine Learning With Python.
Optimization is not only an essential part of machine learning algorithms. It is also the solution to many industrial problems in itself. There are ubiquitous examples of applications that require finding an optimal object from a finite set of things.
Quantum computing beckons with exponential acceleration in solving problems. There’s a problem, though. We can’t just put a problem into a quantum algorithm, and everything is OK.
To use a quantum algorithm, we have to formulate our problem so the quantum algorithm can work. We have to encode the problem we want to solve into qubits.
But, how do we do this? How do we encode an optimization problem into qubits?
Of course, there are myriads of ways to do this. One option is the quantum oracle.
The quantum oracle is a placeholder for a yet unknown quantum transformation gate representing something you want to identify. First, you define an instantiation of the oracle for each possible something. Then, you craft a quantum circuit that produces different outcomes for different oracle instances. As a result, you can tell whether the oracle represented something you looked for.
Simply put, the oracle lets you answer yes or no questions and multiple-choice questions.
But optimization problems are different. We don’t search for a correct answer. We don’t want to put a label on something unknown. But we aim to find the best among many suitable solutions.
This forces us to take a different approach. We have to encode the problem into qubits to allow us to identify a solution and evaluate how good it is.
So, let’s look at how we can do it.
A qubit is a quantum mechanical system, which means it operates according to the rules of the subatomic world. Subatomic things are different from traditional things in that they have wave-like and particle-like characteristics. This is known as the wave-particle duality.
This does not imply that a subatomic thing, such as an electron, is a wave. But, it’s a particle with specific characteristics whose behavior, in some situations, is better explained with the function that is typically used to describe waves.
So, how does a wave behave? In general, a wave moves up and down as it travels. So, it is not a static thing. Instead, it changes over time. Once, we see the wave at its crest at a specific time and place. Then, at another time and place, it is at its average.
So, when you look at a wave at a single point, you may see completely different things. And this is precisely what we experience when working with qubits. When we look at two similar qubits, we may catch them at different points on their trajectory and, therefore, measure them as two different values. When we see one qubit at its crest, it’s a 1. When we catch the second qubit at the mean, it’s a 0.
What we see is not the complete wave. It is a snapshot of the wave. And this is what Max Born formulated in his postulate in 1926:
This is a direct consequence of the qubit state normalization.
It says |α|²+|β|²= 1 for a qubit state
𝛼 and 𝛽 denote the wave’s magnitudes at two different points whose absolute squares specify the probability of catching the wave at that point. These two points correspond to the computational bases of a qubit — its two possible values, 0 and 1. The probability of all possible measurements must be 1 (=100%).
The following image depicts this graphically. 𝛼 and 𝛽 represent the proximities to the basis states.
Consequently, working with qubits is inherently probabilistic. But this does not mean that it is random. By contrast, we can work with the qubit very well. We use quantum operators to put it into a state where specific measurements are more likely than others.
Quantum operators transform one qubit state into another. Let’s look at the NOT operator, for instance.
Mathematically, the X-gate quantum operator is the matrix:
When we apply this operator to different qubit states — we multiply the corresponding transformation matrix by the state vector — we can see that it reverses the amplitudes of |0⟩ and |1⟩.
Reversing state |0⟩ results in |1⟩:
Reversing state |1⟩ results in |0⟩:
Generally, it reverses any arbitrary state:
Furthermore, we can combine quantum operators to create any arbitrary state — as long as it is a valid qubit state. We can create a qubit system that exhibits any measurement probabilities we like.
The usual approach encodes the solution as a quantum oracle that changes the qubit state a little bit. Even though we don’t know the very instance of the oracle, we know its possible effects. Then, we use quantum gates to amplify those tiny differences and end up in different measurements that let us conclude on the exact oracle instance.
But there’s a big problem. The oracle lets us distinguish between states that solve the problem and states that do not. It’s a yes-or-no question. But, in optimization, we search for the best of a whole set of reasonable solutions.
So, we need to follow another approach. And in this approach, we’ll use operators differently.
In quantum mechanics, there are some special operators. The way these operators act on a quantum state corresponds with physical observables, such as the position of a particle, its momentum, spin, and, most importantly, energy. This is known as the correspondence principle.
For example, the Hamiltonian is one of these operators. It describes the possible energies of the quantum system. And the energy is not a Boolean value. It is a real number. Therefore, we can compare two energies and decide which one is bigger.
So, when we formulate the objective function that we aim to optimize as a Hamiltonian, the energy of this system corresponds to the performance of the solution. Then, the optimization is a search for the system’s lowest (or highest) energy.
Don’t miss the next episode and subscribe to my Substack channel.
Do you want to get started with Quantum Machine Learning? Have a look at Hands-On Quantum Machine Learning With Python.
Get the first three chapters for free here.
Practical Quantum Machine Learning
Do you want to get started with Quantum Machine Learning? Have a look at Hands-On Quantum Machine Learning With Python.
Optimization is not only an essential part of machine learning algorithms. It is also the solution to many industrial problems in itself. There are ubiquitous examples of applications that require finding an optimal object from a finite set of things.
Quantum computing beckons with exponential acceleration in solving problems. There’s a problem, though. We can’t just put a problem into a quantum algorithm, and everything is OK.
To use a quantum algorithm, we have to formulate our problem so the quantum algorithm can work. We have to encode the problem we want to solve into qubits.
But, how do we do this? How do we encode an optimization problem into qubits?
Of course, there are myriads of ways to do this. One option is the quantum oracle.
The quantum oracle is a placeholder for a yet unknown quantum transformation gate representing something you want to identify. First, you define an instantiation of the oracle for each possible something. Then, you craft a quantum circuit that produces different outcomes for different oracle instances. As a result, you can tell whether the oracle represented something you looked for.
Simply put, the oracle lets you answer yes or no questions and multiple-choice questions.
But optimization problems are different. We don’t search for a correct answer. We don’t want to put a label on something unknown. But we aim to find the best among many suitable solutions.
This forces us to take a different approach. We have to encode the problem into qubits to allow us to identify a solution and evaluate how good it is.
So, let’s look at how we can do it.
A qubit is a quantum mechanical system, which means it operates according to the rules of the subatomic world. Subatomic things are different from traditional things in that they have wave-like and particle-like characteristics. This is known as the wave-particle duality.
This does not imply that a subatomic thing, such as an electron, is a wave. But, it’s a particle with specific characteristics whose behavior, in some situations, is better explained with the function that is typically used to describe waves.
So, how does a wave behave? In general, a wave moves up and down as it travels. So, it is not a static thing. Instead, it changes over time. Once, we see the wave at its crest at a specific time and place. Then, at another time and place, it is at its average.
So, when you look at a wave at a single point, you may see completely different things. And this is precisely what we experience when working with qubits. When we look at two similar qubits, we may catch them at different points on their trajectory and, therefore, measure them as two different values. When we see one qubit at its crest, it’s a 1. When we catch the second qubit at the mean, it’s a 0.
What we see is not the complete wave. It is a snapshot of the wave. And this is what Max Born formulated in his postulate in 1926:
This is a direct consequence of the qubit state normalization.
It says |α|²+|β|²= 1 for a qubit state
𝛼 and 𝛽 denote the wave’s magnitudes at two different points whose absolute squares specify the probability of catching the wave at that point. These two points correspond to the computational bases of a qubit — its two possible values, 0 and 1. The probability of all possible measurements must be 1 (=100%).
The following image depicts this graphically. 𝛼 and 𝛽 represent the proximities to the basis states.
Consequently, working with qubits is inherently probabilistic. But this does not mean that it is random. By contrast, we can work with the qubit very well. We use quantum operators to put it into a state where specific measurements are more likely than others.
Quantum operators transform one qubit state into another. Let’s look at the NOT operator, for instance.
Mathematically, the X-gate quantum operator is the matrix:
When we apply this operator to different qubit states — we multiply the corresponding transformation matrix by the state vector — we can see that it reverses the amplitudes of |0⟩ and |1⟩.
Reversing state |0⟩ results in |1⟩:
Reversing state |1⟩ results in |0⟩:
Generally, it reverses any arbitrary state:
Furthermore, we can combine quantum operators to create any arbitrary state — as long as it is a valid qubit state. We can create a qubit system that exhibits any measurement probabilities we like.
The usual approach encodes the solution as a quantum oracle that changes the qubit state a little bit. Even though we don’t know the very instance of the oracle, we know its possible effects. Then, we use quantum gates to amplify those tiny differences and end up in different measurements that let us conclude on the exact oracle instance.
But there’s a big problem. The oracle lets us distinguish between states that solve the problem and states that do not. It’s a yes-or-no question. But, in optimization, we search for the best of a whole set of reasonable solutions.
So, we need to follow another approach. And in this approach, we’ll use operators differently.
In quantum mechanics, there are some special operators. The way these operators act on a quantum state corresponds with physical observables, such as the position of a particle, its momentum, spin, and, most importantly, energy. This is known as the correspondence principle.
For example, the Hamiltonian is one of these operators. It describes the possible energies of the quantum system. And the energy is not a Boolean value. It is a real number. Therefore, we can compare two energies and decide which one is bigger.
So, when we formulate the objective function that we aim to optimize as a Hamiltonian, the energy of this system corresponds to the performance of the solution. Then, the optimization is a search for the system’s lowest (or highest) energy.
Don’t miss the next episode and subscribe to my Substack channel.
Do you want to get started with Quantum Machine Learning? Have a look at Hands-On Quantum Machine Learning With Python.
Get the first three chapters for free here.
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.