New Solver for Sampling or Satisfaction

[Bhaney44]

Current Problem Yes. I have a problem where I am struggling to find the right way to program my question to the quantum computer.

Proposed Solution

I have a 32-bit output generated from an unknown 4-bit binary input. For example:

IN: abcd OUT: 01234567

I need to ask the quantum computer: for a specific given output, for example,76543210, what was the input?

Alternatives Considered

There are at least two ways to solve this problem. The first is with a sampling problem, where the quantum computer samples every possible arrangement of the 4-bit input until it arrives at the proper output. The second is as a constraint satisfaction problem, where the quantum computer samples 4-bit input arrangements to find the input that satisfies the output constraints.

Approach 1.

from dwave.system import DWaveSampler
sampler = DWaveSampler()
for i in range(0,1):
    qubit_0 = sampler.nodelist[0]
    qubit_1 = next(iter(sampler.adjacency[qubit_0]))
    qubit_2 = next(iter(sampler.adjacency[qubit_1]))
    qubit_3 = next(iter(sampler.adjacency[qubit_2]))
    input = [qubit_0, qubit_2, qubit_3, qubit_4]
    output = f(input)
    solution = 76543210
    if output == solution:
        print(input)

One problem with Approach 1 is the qubits need to each be a random sample that return a binary, Boolean, format. It would be great if the computer could solve the problem in parallel, where it could test -1, 0, and 1 for each qubit simultaneously.

Approach 2.

import dwave_networkx as dnx
input = dnx.chimera_graph(1, 1, 1)
output = dnx.chimera_graph(1, 1, 4)

One issue with Approach 2 is adding logical constraints to the problem. The problem is purely mathematical, but a graph architecture may be the best way to solve it because there are clear output constraints.

Additional context I am working on finding the right Python Documentation to solve this problem. I found the documentation on Stating the Problem and Reformulating the Problem. I will continue updating this feature request as I make progress toward the solution, a proper question for the quantum computer.

In the meantime, I would be grateful for any advice, suggestions or guidance; thank you!

[Bhaney44]

Definitions from the D-Wave Docs.

[Bhaney44]

I am still working through this problem. I wrote out some math that needs reformulated as a QUBO or ISING problme.

[Bhaney44]

The objective function is a minimization problem. Any given variable x is a binary variable. I need to find the value of x at which y takes its minimum value. Then, the issue is solving for f. So I will need to formulate f as a series of QUBOs.

[Bhaney44]

One solution is Grover's Algorithm. I was able to run Grover's algorithm on the D-wave machine. I'm not sure if this has been done before, but I am worried I still need a logical breakthrough for full convergence.

In:

import matplotlib.pyplot as plt
import numpy as np
import string
import hashlib
from math import sqrt, pi
from collections import OrderedDict
from statistics import mean
  
def ShowGraph(amplitude_value, n):
    y_position = np.arange(n)
    plt.bar(y_position, amplitude_value.values(), align='center', color='g')
    plt.xticks(y_position, amplitude_value.keys())
    plt.ylabel('Amplitude Value')
    plt.title('Grovers Algorithm')
    plt.show()

def GetOracle(xvalue):
    return hashlib.sha256(bytes(xvalue, 'utf-8')).hexdigest()

def ExecuteGrover(target, objects, nvalue, rounds):
    y_pos = np.arange(nvalue)
    amplitude = OrderedDict.fromkeys(objects, 1/sqrt(nvalue))
  
    for i in range(0, rounds, 2):
        for k, v in amplitude.items():
            if GetOracle(k) == target:
                amplitude[k] = v * -1
  
        average = mean(amplitude.values())
        for k, v in amplitude.items():
            if GetOracle(k) == target:
                amplitude[k] = (2 * average) + abs(v)
                continue
            amplitude[k] = v-(2*(v-average))
    return amplitude

target_algorithm = '1'
objects_grover = ('4', '5', '1', '7','9','11','97')
number = len(objects_grover)
amplitude_grover = OrderedDict.fromkeys(objects_grover, 1/sqrt(number))

amplitude_grover[target_algorithm] = amplitude_grover[target_algorithm] * -1
print(amplitude_grover)
average_grover = mean(amplitude_grover.values())
print("Mean is {}".format(average_grover))
for k, v in amplitude_grover.items():
    if k == target_algorithm:
        amplitude_grover[k] = (2 * average_grover) + abs(v)
        continue
    amplitude_grover[k] = v-(2*(v-average_grover))
print(amplitude_grover)

needle_value = "#000000000000000000068983c42ee2e725ea9f07a2ec71ea7d7b2df133077ee2"
haystack_value = string.ascii_lowercase
num = len(haystack_value)
num_rounds = int((pi / 4) * sqrt(num))
print("number of rounds are {}".format(num_rounds))

Out:

Leap IDE /workspace/rna-folding/tests $ python3 tests.py
OrderedDict([('4', 0.3779644730092272), ('5', 0.3779644730092272), ('1', -0.3779644730092272), ('7', 0.3779644730092272), ('9', 0.3779644730092272), ('11', 0.3779644730092272), ('97', 0.3779644730092272)])
Mean is 0.26997462357801943
OrderedDict([('4', 0.16198477414681167), ('5', 0.16198477414681167), ('1', 0.9179137201652661), ('7', 0.16198477414681167), ('9', 0.16198477414681167), ('11', 0.16198477414681167), ('97', 0.16198477414681167)])
number of rounds are 4

[djohnson-dwavesys]

Hello, We would like to ask you to please post these questions in the Leap Community forums: https://support.dwavesys.com/hc/en-us/community/topics This is a great way to connect with other users, browse available information, and get help from our Support team. The Practical Applications or Coding Tips and Tricks sections might be good spots to ask some of these questions. The GitHub Issues section is more geared towards code changes and bugs. Thank you for your understanding and interest!

[Bhaney44]

How do I include code blocks in the Leap Community forum? @djohnson-dwavesys

[Bhaney44]

Link to the problem in the community forum.