Program to find the optimal assignment of passengers to drivers/cars based off of the requested leave times and the respective locations of the drivers and passengers.
To get started with the repository, you need to do the following:
Clone the repository to your system:
$ git clone https://github.com/Tiernan8r/driver_assigning
Move into the cloned repository:
$ cd driver_assigning
Setup a python virtual environment:
$ python -m virtualenv venv
Activate the new virtualenvironment
$ source venv/bin/activate
Download the PyPi program requirements:
$ pip install -r requirements.txt
Verify that all the tests are working, by running:
$ pip install -r test-requirements.txt
$ tox
There are three test actions configured for the repository, tests
/pep8
/
mypy
.
The individual actions can be run using
$ tox -e [action]
where [action]
is one of tests
/pep8
/mypy
Once you have the repository set up on your system, you can run the code using one of the following:
The Help message for the CLI gives an overview of the program usage
$ ./qcp/main.py -h
USAGE:
./qcp/main.py [FLAGS] nqbits
FLAGS:
-a/--algorithm The quantum algorithm to simulate, can be one of:
g = Grover's Algorithm
pe = Phase Estimation
s = Toy Sudoku solver
Defaults to 'g' if unset
-h/--help Display this prompt
-g/--gui Display the GUI.
The CLI options vary by choice of algorithm:
GROVERS:
USAGE:
./qcp/main.py --algorithm g [FLAGS] nqbits
ARGS:
nqbits The number of qbit states to simulate, must be >= 2.
FLAGS:
-t/--target The target state, defaults to 0
PHASE ESTIMATION:
USAGE:
./qcp/main.py --algorithm pe [FLAGS] nqbits
ARGS:
nqbits The number of qbit states to simulate, must be >= 2.
FLAGS:
-p/--phase The phase to use for the Phase Shift Gate (if using).
defaults to 0.25.
-u/--unitary The choice of unitary gate to simulate with, can be
one of the following:
* H = Hadamard Gate
* P = Phase Shift Gate (requires the -p flag)
Defaults to 'H' if unset
SUDOKU:
USAGE:
./qcp/main.py --algorithm s
ARGS:
None
FLAGS:
None
As you can see, the program is capable of simulating three different quantum algorithms and use cases.
nqbits
: is a required parameter, and controls the number of qbibts to simulate in the simulator
Note: The quantum simulator simulates matrices of size
2^nqbits
, so be aware that The simulation takes exponentially longer for each extra qbit simulated.
-t
/--target
: is the target state to search for, must be bounded within 1 < t < 2^nqbits
nqbits
: is a required parameter, and controls the number of qbibts to simulate in the simulator
Note: The quantum simulator simulates matrices of size
2^nqbits
, so be aware that The simulation takes exponentially longer for each extra qbit simulated.
-u
/--unitary
is the unitary matrix to use in the phase estimation algorithm, currently there are two choices:
* H = Hadamard Gate
* P = Phase Shift Gate
Note: When the Phase Shift Gate is chosen, the phase to shift by can be overwritten using the
-p
/--phase
flag.
A sample application of Grover's Algorithm, where we solve the toy problem of a 2x2 sudoku. Takes no input
A Graphical User Interface (GUI) is provided with the program to make interaction with it easier.
The GUI can be initialised with the following command:
$ ./qcp/main.py -g
This will bring up the GUI, defaulting to Grover's Algorithm.
At the top of the GUI is a drop down list, with the options for the algorithms to simulate, choosing each algorithm in sequence will update the GUI to reflect the input parameters of that algorithm
Grover's Algorithm has two input fields.
The first field sets the number of qbits to simulate.
The second is the target state, and is bounded within 0 < t < 2**nqbits
The phase estimation is the most complicated GUI element.
As with Grover's Algorithm, the first input is the number of qbits to simulate.
The phase estimation then requires input of two matrices, a unitary matrix, and an eigenvector.
To help with this input, the GUI has helper elements to select some defaults.
For the Unitary Matrix, a dropdown element is present that allows the user to select two pre-defined
matrices, the HADAMARD
gate, or the PHASE_SHIFT
gate.
When the drop down list is changed, the table showing the matrix is updated with it's values.
For the PHASE SHIFT
gate, two new GUI elements also appear, that allows the user to set the
phases in the two diagonal elements:
Once the user has selected a unitary matrix, they can then follow similar steps to select an eigenvector:
The dropdown list for the eigenvectors changes per choice of unitary matrix:
For the HADAMARD
gate, the two choices are the bases |+>
& |->
.
For the PHASE SHIFT
gate, the two choices are the bases |0>
& |1>
.
Of course, the user can always input custom matrices manually, and the GUI will perform checks on the validity of the matrices before beginning the simulation,
Any integer
/float
/complex
is an acceptable parameter.
If there are any issues with the inputs of the two matrices once the simulation is set to start, the simulation will quit and a useful error message will appear beside the matrix at fault with a message pin-pointing the entry at fault.
At the bottom of the UI element, there are two extra fields: Precision & Success Rate, these determine the number of decimal points we want to estimate the phase to (the "precision"), and the acceptable rate that the results could be inaccurate ("success rate")
If the user wishes to get a more acceptable answer, they can input their parameters, and click the determine button, in which case the UI will calculate the number of qbits to use to get this accuracy, and auto-set the number of qbits field.
The sudoku has no explicit input, which segues nicely to:
Once ready to begin running the quantum algorithm simulation, click the button at the bottom of the GUI labeled "search" or "start".
This will begin the simulation of the chosen algorithm in the background.
While the simulation is running, a visual indicator will appear to show that the simulation is still in progress
Once the search is completed, a plot of the probability of the quantum state being in the target state will be shown on the right.
Grover's Algorithm
As shown in the figure above, the simulation results for Grover's Algorithm also outputs the number of iterations that the quantum simulator took to find the result, and compares it to the equivalent for a classical algorithm.
Phase Estimation
When the phase estimation result is computed, the probabilities are shown in the graph on the right for each state.
Sudoku
Sudoku also outputs a probability distribution in the graph on the right.
For the simple 2x2 sudoku problem, a sample layout is also shown in a table, with the probability calculated by the algorithm for that state to be the accepted result.