## Challenge Overview

# Introduction

We have run a series of quantum computing learning challenges. Now, let’s go beyond those toys and look at a real-world problem. We are looking for efficient solutions that can solve the max-cut problem using the provided Fujitsu’s Digital Annealer platform! We hope to receive wonderful solutions.Good Luck!

# Requirements to Win a Prize

In order to receive a prize, you must do the following:- Achieve a score in the top 5, according to system test results calculated using the test dataset. The score must be higher than 0.0. See the “Data Description and Scoring” section below.
- Within 7 days from the announcement of the contest winners, submit a complete 2-page (minimum) report that: (1) outlines your final algorithm and (2) explains the logic behind and steps of your approach.

# Objective

We have run Max-Cut problem on previous learning challenge (https://tc3-japan.github.io/DA_tutorial/tutorial-3-max-cut.html). In the Max-Cut problem, there are N nodes and M weighted edges. The goal of this problem is to partition these nodes into two parts to maximize the total edge weights between these two parts.As mentioned, DA can solve up to 8192 bits of solution space. We will be limiting the use to

__.__

**1024 bits**A typical max-cut solver in DA requires n binary variables, representing whether each node belongs to the first part. A tutorial challenge hosted was for the max-cut problem at a small scale that fits into this solution space. In the real world, the number of nodes can become quite large that do not fit into the solution space of DA.

In this challenge, we are going to solve the max-cut problem on much larger graphs of 2,000 and 5,000 nodes! This will need some algorithm that can solve a large number of nodes that do not fit into the limited solution space, naturally calling DA API multiple times.

The goal is to obtain a bigger cut value as much as possible within the timeout window of 3 minutes. If the cut value is the same, faster execution time wins.

# Implementation

Implementation details will be the same as the tutorial challenge #3 - Max Cut. Please review the tutorial at this URL: https://tc3-japan.github.io/DA_tutorial/tutorial-3-max-cut.htmlIn brief;

- You are asked to implement a function main(n_node, edges) that returns 2 groups of nodes.
- You can call the function solveDA(rule, da_params) multiple times with request and response as mentioned in the tutorial.
- Note that you will need to have BinaryQuadraticPolynomial class in your python script in addition to the above functions.

Python (3.6) is the only language allowed for this Marathon Match. You can use only the default libraries, NumPy (1.15.4), and SciPy (1.2.1) which is installed in the execution system.

Create a

__single__python script file, zip it, and submit to Topcoder platform during the submission phase. The platform will run your script and return the results via email. Make sure that your email registered with Topcoder is accurate and up to date.

# Scoring

Scores range from 0.0 (worst) to 100.0 (best). For each test case, we want to maximize the cut value you find. If the score is the same, a smaller execution time wins.

The time limits for each test case are

__3 min__(180 sec.).Therefore, suppose you find a cut value using T seconds, and the max known cut value for the test data set is MAX, the score of this test case will be:

*score = (your_cut_value - T/180) / MAX * 100.0*

The

__total score__will be the average of the scores on all tested graphs.In the

__Provisional Test__, we will use 2 graphs with 2,000 and 5,000 nodes. Meaning your main function will be called 2 times, each having 180sec. time limit.In the

__System____Test__we will use different graphs with 2,000 and 5,000 nodes.The nodes for all datasets are randomly generated with the same density for all 2,000 sets, also the same density for all 5,000 sets. The edge weights are all 1.

Note:

- As you can imagine, there is small pre- and post-process when calling DA API that your script does not have control of. To make this a fair scoring, the execution time mentioned above will remove this overhead. So, T = (actual execution time of your script) - (DA API wait time) + (only the annealing time within DA).
- Also, we will be using a slightly higher value than the actual max known cut value for the MAX mentioned above. So, we have enough space in case you find a better value!
- Due to how the scoring platform is hooked up with DA API, your scripts will be run one by one with other participants’ script. This means that your script will be put in a FIFO queue to run, and you might not be getting the results back immediately.

# General Notes

- This match is
__rated__ - The allowed programming language is
__Python only__ - The memory limit is
__128 MB__ - The source code size limit is
__6 MB__ - Each script needs to run within
__180 sec.__for each test case - Each member can make a maximum of
__30 submissions__for this challenge - You can only submit once per
__60 minutes__ - The script must cut the given graph into 2 parts
- Once you have submitted the script, the system will send you multiple emails. After your script has been executed against DA, the system will send you the last email with results from "TC3-QuantumScorer" reviewer. Overall result and a unique URL will be returned where you will be able to download a file containing all the request/response of DA API calls
- You can include ONLY open source code in your submission, provided it is free for you to use and would be for the client as well. Code from open source libraries under the BSD or MIT licenses will be accepted. Other open source licenses may be accepted too, just be sure to ask us.
- Use the match forum to ask general questions or report problems, but please do not post comments and questions that reveal information about the problem itself, possible solution techniques or related to data analysis.