Weighted coins and linear algebra
[Since the forum is in an early stage, I just throw all my considerations in one post here]
1. Is it possible to represent a real number by a qbit? I have encountered here an example of random number generator, equivalent to tossing some coins. As far as I understood it was possible by setting all the weights (energy coefficients?) to zero. Then the question arises, is it possible to toss a set of weighted coins? For example, we would like to toss a weighted coin, which gives 1 with probability p and 0 with probability 1-p. How could it be done on D-Wave?
2. If the answer to 1. is positive, then (at least in principle) we could represent a real number b (in the range [0,1], but that probably could be scaled to arbitrary interval) by a Constraint Satisfaction Problem x-b=0. Or in other words b would be represented as a weighted coin with probability corresponding to 1 equal to b. Then running the CSP many times, we would obtain an approximation for b based on statistics of the discrete outcomes x (equal 0 or 1). If that is correct we could approximately solve a linear equation using 1 qbit (in multiple runs).
3. If the statement above is correct, how one could represent linear algebra operations, e.g., matrix multiplication? Since the operation is still linear, I assume one could adjust the energy minimization problem to solve it, just using multiple qbits this time. This are already far reaching considerations, but solving linear systems is an important issue. Usually, the solution strategy and particular implementation is based on a prior knowledge about the system. As the number of qbits in available QPUs grow, at some point it might be possible to find a rough approximate solution of a linear system or an eigenvalue problem using QPU. This rough approximate solution might be used as a starting point for classical algorithms then. Are there already any successful attempts to use QPUs for linear algebra?
Comments
Hello!
Thank you for your interest! It's awesome to see people get excited about the QPU and it's capabilities!
It's possible that someone has taken a look at this.
I have asked around and will let you know what I manage to dig up!
This is definitely something I personally have given some thought, or at least something similar, in the context of factoring large numbers in the context of prime numbers, but I haven't had a chance to experiment with it too much.
It might be a bit difficult to do, in that you would be looking for the probability from the distribution, and this would have a low accuracy in general.
The rules of big number theory apply as the number of experiments approach infinity.
That said, it could be something that might yield useful behaviour.
Give it a shot and let us know what you find!
I'm not sure if it will be completely useful, but you might want to take a look at the Getting Started Guide:
https://docs.dwavesys.com/docs/latest/doc_getting_started.html
You might also find the Leap Quantum Coding Challenges interesting.
There are problems starting with simple ones and getting progressively more difficult.
https://support.dwavesys.com/hc/en-us/community/topics/360000871833
To better understand the QPU's Chimera graph connectivity, these two links are a good introduction:
https://docs.dwavesys.com/docs/latest/c_gs_4.html
https://docs.dwavesys.com/docs/latest/c_gs_7.html
There is also a relatively simple example of representing constraints on the QPU (although I know your example above is a little different):
https://docs.dwavesys.com/docs/latest/c_gs_6.html
As for getting to an initial low energy state using the QPU and then using classical computing to further optimize, we have recently added this functionality to dwave-hybrid:
https://github.com/dwavesystems/dwave-hybrid/blob/master/examples/tabu-postprocessing.py
I hope this is helpful!
I was informed of a paper that might be relevant:
https://arxiv.org/abs/1903.05068
This paper is about representing integer values, but it might prove to be useful.
I was also giving some thought to some of the setbacks to representing the value b, and I thought I would link the ICE (Integrated Control Error) documentation:
https://docs.dwavesys.com/docs/latest/c_qpu_ice.html
Reading through this documentation you will see the error in precision and integrity, which will make obtaining consistent floating point values in this way difficult.
That said, the usual types of calculations done using the QPU do not suffer in the same way due to these errors.
Please sign in to leave a comment.