~rd/qjudge

QJudge is like ejudge, but for quantum algorithms.

#Table of Contents

Usage
Terminology
Installation
Running
Checkers
Valuer
Standard checkers
1. Simple checker
2. Oracle checker
Components
1. Quirk
Supporting
Commercial license
Author

#Usage

Example installation runs at https://qjudge.gltronred.info

To get a user account please contact me and tell how do you want to use QJudge.

#Terminology

Problem - a task that user (participant) has to solve. Solution usually involves using UI. Problems are prepared by teacher. Problem has description and tests.
Submission - a solution for problem. Submission is tested on a predefined set of tests.
UI for submission - different problems can have different interfaces for participants (e.g. Quirk for circuit or some textbox for writing a program in Qiskit).
Test - a pair of input and correct value, or a pair of input and some criteria whether output is correct. Submission is given the input value and it produces an output value. The output value should be correct in order to pass the test. Teacher prepares tests for the problem.
Checker - a program that checks, whether the output value is correct for given input value. Some standard checkers are provided, otherwise teacher should write the checker program.
Valuer - some tests can be more important than other, so valuer combines verdicts of the tests.

#Installation

Compile server part: cabal update; cabal install. Requires GHC 9.2
Compile quirk UI: cd assets/quirk; npm run build; cd -
Compile main web part: cd assets/qjudge-main; npm run build-only -- --mode production; cd -
Copy qjudge-server, qjudge-worker executables, checkers from checkers, and html pages from assets/quirk/out/quirk.html and assets/qjudge-main/dist/ to the destination.

#Running

QJudge has two executables: qjudge-server and qjudge-worker.

#Server

Server provides user interface and accepts submissions from users. It writes submissions to the faktory queue.

Usage: qjudge-server <config.json>

#Worker

Worker fetches submissions from the faktory queue, runs a checker on them and writes back the results.

Usage: qjudge-worker --worker <queue-name> | --single <submission-id>.

#Configuration

Configuration file is a JSON. Its format is described in Types.hs.

{
    "port": 1234,
    "database": "production.db",
    "faktory_password": "p4$$w0rd",
    "queue": "faktory_queue"
}

Faktory password is optional, but it is required for production environment

#Running faktory

You can get faktory as docker image and run it: docker run --rm --publish 7419:7419 --publish 7420:7420 contribsys/faktory.

For production you have to set a password: sudo docker run --rm -it -v faktory-data:/var/lib/faktory -e "FAKTORY_PASSWORD=p4$$w0rd" -p 127.0.0.1:7419:7419 -p 127.0.0.1:7420:7420 contribsys/faktory:latest /faktory -b :7419 -w :7420 -e production

#Checkers

Checkers check correctness of user’s submission.

Currently, qjudge-worker launches a checker defined in the problem. The checker and the worker communicate by the following protocol.

The worker sends to standard input of the checker the following information:

first line contains circuit in the quirk format (a string representing JSON that quirk exports);
second line contains an integer T;
the next T lines are test descriptions.

The checker writes to standard output the verdict for the circuit and for each test. The verdict is one of:

OK (means mark is 100)
FAIL (means mark is 0)
MARK <m> (mark is m, where 0 <= m <= 100)
RAW <r> (raw value, r can be any integer, positive or negative)
CF (check failed: checker is in impossible situation, has to be rewritten; checker MUST write a comment for this verdict)

If checker does not write a verdict, it is CF.

Checker can write a comment for any verdict by appending it after colon (e.g. MARK 50: something is not correct, but otherwise ok). System shows the comment to the participant.

The checker may write logs to standard error in any format. These logs are not available to participant.

We proposed this design for its simplicity: one should not think about exception handling etc., if some test fails, checker fail and QJudge takes care to set failed status.

Regarding job queue. We define job to be a program because compiling circuit is time-consuming operation, so we don’t want to repeat it for each test.

#Valuer

After checking the submission, system gets a sequence of verdicts and combines them to a value of the submission.

If any of the verdicts is CF, the submission is CF.

System converts all OK and FAIL verdicts into MARK 100 and MARK 0 correspondingly. Checker SHOULD NOT mix marks and raw values for different submissions on the same test.

Suppose that we have a set ${M_i}$ of marks, $1 \le i \le N_m$ and a set ${R_i}$ of raw values, $1 \le i \le N_r$.

For each test $i$ that returns raw values, we normalize raw values from the interval $[R_{min}; R_{max}]$ to be in the interval $[0; 100], where $R_{min}$ and $R_{max}$ are minimal and maximal raw value in all submissions from all participants for this test. Let $V_i$ be a normalized value for raw value $R_i$.

Note. When computing raw value range we filter out all non-raw results. Therefore, if verdicts are mixed, the score uses only some of verdicts, and scores of different submissions are incomparable.

We compute sum $M$ of marks and sum $V$ of normalized values: $$ M = \sum_{i=1}^{N_m} M_i, $$ and $$ V = \sum_{i=1}^{N_r} V_i. $$

Final mark for submission is $W_m M + W_v V$, where $W_k$ are weights for marks and normalized values (they are defined for each problem separately).

#Standard checkers

#Simple checker

Each test is a JSON object describing circuit input state and required output state.

Test has the following fields (all fields except options are mandatory):

input: description of an input state;
output: description of an output state;
options: optional field describing comparing options.

Options object can have the following optional fields:

eps: precision for comparing numbers (default: 1e-6).
max_depth: not implemented: maximum depth of circuit (default: 1000)
max_width: not implemented: maximum number of qubits (default: 16)

Input is a JSON object with (exactly) one of the following fields:

base: string that contains a base state

Length of the base state determines the width of the input.

Output is a JSON object with (exactly) one of the following fields:

base: base state (zero-one string);
ampl: array of complex numbers - amplitudes of states in lexicographic order;
sub_ampl: map with keys - base states and values - complex numbers. Checker checks only some of states (other amplitudes are not checked);
prob: array of ProbabilityRequirement objects for some subsets of states (other amplitudes are not checked).

Representation of a complex number is an array with two double-precision numbers - real and imaginary parts.

ProbabilityRequirement is a JSON object with the following fields:

states: array of states (zero-one strings);
req: one of strings: "EQ", "LT", "GT";
prob: double-precision number - a probability.

#Oracle checker

The task declares oracle gates that users should use in their submission.

Checker provides an implementation of the oracle gate.

Tests have the same fields as simple checker. Additionally, test can have oracles field with an array of gates (in Quirk format). These gates are substituted instead of gates defined in task.

To define the gates that should be used in the submission, UI for submission should define gates field (in Quirk’s format)

#Components

#Quirk

UI for submission uses Quirk, made by Craig Gidney aka Strilanc, licensed under Apache 2.0 license.

Changes that I made to Quirk:

removed gates that are not supported by Cirq from toolboxes;
turned off menu with examples;
added a button to send exported circuit to the server;
added a field that receives a text of a problem to be solved.

#Supporting

If you like this software and want to help me develop it, you can support me.

If you donate a regular donation, I will be

able to devote more time to developing and supporting this project.

It is well known that mathematicians and programmers use coffee as a fuel ☺

and you can buy me a coffee to support my work.

#Commercial license

This software is licensed under Affero GPL v3 or any later version. This means that if you use the unmodified software on your server or if you modify the software you have to provide the source of the software (or its modified version).

If use of the software under this license does not satify your organization’s legal department, we can discuss commercial licensing. Please contact me.

#Author

If you have any other questions, please don’t hesitate to contact me directly: @gltronred or gltronred@pm.me.

You can also:

Report bugs and submit feature requests to the issue tracker
Subscribe to mailing lists and ask any questions
Explore the source code of the program

You can support my work on liberapay (regular donations) or buymeacoffee (one-time donation).

refs

clone