Abstract:
This thesis has two main parts.
In the first part, we develop tools for distinguishing quantum random
strings generated by quantum experiments certified by the Kochen-
Specker theorem from random strings generated by classic algorithms.
This analysis is important and essential because the theoretical certification
has to be validated experimentally to be physically relevant.
Instead of standard randomness tests that check the specific properties
of strings of bits, our tests focus on indirectly identifying evidence of
incomputability, which distinguishes quantum random sequences from
pseudo ones. Variants of Solovay-Strassen primality tests based on the
Chaitin-Schwartz theorem are implemented. Even though some of the
tests are capable of showing differences, conclusive differences have not
been identified. This indicates that further study is needed to overcome
the difficulty of observing incomputability in quantum random strings.
The results in this part have been published in [10].
The aim of the second part is to develop quantum algorithms that solve
the maximum common subgraph isomorphism problems. Three quantum
annealing algorithms have been developed, proved correct, and
analysed based on different properties to be maximised. Tests have
been performed on a D-Wave machine (which is a quantum annealing
type of quantum computer). The tests showed that the current
quantum machine could solve toy problems with high enough accuracy.
More experiments with new versions of the quantum machine and the
use of proposed quantum algorithms in practical applications are interesting
problems to be further studied. The results in this part have been published in [93, 92].