Solving a Secret Santa SAT Problem with Classiq

Welcome to my third blog in this series on how to solve a Secret Santa problem using quantum computers. 

This year I want to show how easy it is to generate Q# code to solve the problem using the Classiq platform.

This blog is part of the Q# Holiday Calendar 2022.

Let’s first see what the problem was.

We have 3 or more people who want to play Secret Santa. They all put their name on a piece of paper, and all the papers go into a bowl. After a shuffle, each player will pick a piece of paper, and given that no one has their own name, each player has a name for which he has to buy a present and/or write a poem.

This can be easily visualized using this table, in this case we have 3 players.

In this case if X1 = 1, Vincent has to buy Shai a present.

To satisfy this problem you must have exactly one value in each row and each column. We can write this as a SAT problem like this:

(X1⊕X2)∧(X3⊕X4)∧(X5⊕X6)∧(X3⊕X5)∧(X1⊕X6)∧(X2⊕X4)

For a more detailed description check my first blog post here.

Bring in Classiq

Classiq allows end users to generate efficient logical quantum circuits from a high level language. We can use the Classiq platform to generate a circuit which can solve this challenge, without thinking about qubits or low level gate based programing. We can use either the Python SDK, which we will use below, or a textual model to create these logical quantum circuits.

Let’s see how we can do this.

Firstly let's create the SAT formula as a Python string:

formula = """(    
    ( ( x1) ^ ( x2) ) and
    ( ( x3) ^ ( x4) ) and
    ( ( x5) ^ ( x6) ) and
    ( ( x3) ^ ( x5) ) and
    ( ( x1) ^ ( x6) ) and
    ( ( x2) ^ ( x4) ))"""

Next, let’s create an Arithmetic Oracle to solve the SAT problem:

# Each value can either be 0 or 1 so we use a register size of 1 
qubit.register_size = RegisterUserInput(size=1)

# To solve the SAT problem here we are going to do a search using the Grover method.
# We define the register size per variable, in this case that is always 1.
# Lastly we can either use a “Naive” or “Optimized” approach for uncomputating and freeing intermediate qubits,
# here we use “naive” for clarity of the solution.

grover_params = GroverOperator(
	oracle=ArithmeticOracle(        
  	expression=formula,        
    definitions={
      "x1": register_size,
      "x2": register_size,
      "x3": register_size,
      "x4": register_size,
      "x5": register_size,
      "x6": register_size
    },        
    uncomputation_method="naive"    
  )
)

What we see here is that we first set the register size to 1, this means that each variable can only take the value 1 or 0. Next we load the formula into the ArithmeticOracle.

To actually create a circuit from this, we will pass this oracle to Classiq's synthesis engine like this:

# We want to minimize the number of qubits that we use so we optimize for width
constraints = Constraints(optimization_parameter="width")
preferences = Preferences(backend_service_provider="Azure Quantum", backend_name="Ionq",output_format=["qs"]
model_designer = ModelDesigner()
model_designer.GroverOperator(grover_params)
circuit = model_designer.synthesize(constraints=constraints,preferences=preferences)

Multiple things are happening here so let’s walk though each:

• First, we define an optimization parameter. This will tell the synthesis engine to create the circuit which uses the least amount of qubits. 
• Secondly, we pass the specification of the backend to the synthesis engine. This will make sure we do not use more qubits than the device has. The device we have selected here is the Ionq.qpu device in Azure Quantum. We will also optimize the circuit taking into account the native supported gate set and the QPU topology. Here we also specify the output format, saying that we want to get Q# code as output.
• Next, we add the oracle to our ModelDesiger instance.
• Lastly, we create the circuit given the functionality, the oracle, and the constraints/preferences.

Let’s have a look at the Oracle after running the synthesis engine that is generated below or here.

Now that we have the oracle, we also want to have a look at the Q# code for this oracle. 

With 'circuit.qsharp' we can get the Q# code that is generated, available here.

Now that we have everything in place it is time to execute the program which can be done like this:

cred = AzureCredential(
    tenant_id="",
    client_id="",
    client_secret="",
)

azure_preferences = AzureBackendPreferences(
    backend_name="ionq.simulator",
    credential=cred,
    location="",
    resource_id="",
)


res_azure = Executor(
    backend_preferences=azure_preferences
).execute(circuit)

Now you are curious who has to give who a present, so here is the output which can be found with 'res.result':

{'X1': 0.0, 'X2': 1.0, 'X3': 1.0, 'X4': 0.0, 'X5': 0.0, 'X6': 1.0}

Which means Vincent will get Simon a present, Shai will get Vincent a present and lastly, Simon will get Shai a present.

This shows how easy real-world, functional Q# code can be generated and executed using the Classiq platform.