How to Solve LCS (Longest Common Subsequence) in DWave
I would like to use qunatum computing for the below problem statement
There are list of arrays upto n
a1= [a,b,c,d,e]
a2= [a,b,d,e]
a3= [a,e]
a4=[a,e]
a5=[a,b,c,d,e]
The output should give the maximum common grouping items like, for a1 and a5 both are an exact match
a1 and a2 are matching except c and a3 a4 are exact match
so there can be one group which will give an output of exact match and close match which would be a1 a2 and a5 (they are having only 1 element in difference)
another group would be a3 and a4
How can we solve this in DWave programming
What would be the similar examples available in DWave example library
Comments
Hello,
On first inspection this doesn't look like it would be a good fit for Quantum Annealing, aside from maybe some clever use of the system for optimization. The problem can be solved classically in polynomial time, so the potential for a big win in execution time doesn't seem likely, generally speaking.
If you are interested in trying out some original optimization solutions, feel free to give it a try and reach out to us with questions.
Thank you for your response.
We want to understand this in more detail as to why this problem is not a good fit for quantum annealing. Would you be able to connect with us via phone or email if so I can share my details?
Hello,
Let me first provide a bit more of a detailed explanation:
(1) The constraints needed to specify that the solution "must be common to both inputs" and "must be a sequence" would use up a lot of qubits, leaving not-very-many qubits for representing the actual problem. So overall the input that could be represented on current-sized chips would be fairly small in terms of number of variables.
(2) This is a polynomial-time problem, which means that classical algorithms are available to solve it, and those classical algorithms would be very fast on small problems. D-Wave systems have lower bound times of (at least) tens of milliseconds needed for programming the quantum chip, and because of that lower bound we don't expect to beat classical when inputs are both easy (polynomial) and small.
If you still have questions, we can set up a call to discuss this further.
There are some NP-hard problems relating to strings on Wikipedia:
These might be good problems to look at to get an idea of what problems can benefit from the QPU.
You can also take a look at our collection of examples to see different problems and their implementations.
Thank you, now we have moved to traditional computing for the above problem,
Now we are exploring the job shop scheduling problem,
but that is not working for below inputs
Why below input it not working
jobs = {"cupcakes": [("mixer", 1), ("oven", 4)],
"smoothie": [("mixer", 1), ("oven", 3)],
"lasagna": [("oven", 2)]}
max_time = 10
same is the case with
jobs = {"group1": [("man", 2), ("women", 1)],
"group2": [("man", 1), ("women", 2)],
"group3": [("man", 2), ("women", 1)]}
Can this be possible that if we have any n number of input and we can pass max number as worst case which can be derived from sum of all unique so that qunatum will provide me the best possible solution.
https://github.com/dwave-examples/job-shop-scheduling
Please sign in to leave a comment.