José Javier Paulet González

In simulating Quantum Computing by using the circuit model the size of the matrices to deal with, together with the number of products and additions required to apply every quantum gate becomes a really hard computational restriction. This paper presents a data structure, called Functional Matrices, which is the most representative feature of QSimov quantum computing simulator which is also provided and tested. A comparative study of the performance of Functional Matrices with respect to the other two most commonly used matrix data structures, dense and sparse ones, is also performed and summarized within this work.

The SAT problem is maybe one of the most famous NP-complete problems. This paper deals with the 3-SAT problem. We follow a sort of incremental strategy to save computational costs with respect to the classical quantum computing approach. We present an heuristics that leads this strategy, improving the performance of the purely random incremental scheme. We finally validate our approach by means of a thorough empirical study.

Graph Isomorphism is such an important problem in computer science, that it has been widely studied over the last decades. It is well known that it belongs to NP class, but is not NP-complete. It is thought to be of comparable difficulty to integer factorisation. The best known proved algorithm to solve this problem in general, was proposed by L\'aszl\'o Babai and Eugene Luks in 1983. Recently, there has been some research in the topic by using quantum computing, that also leads the present piece of research. In fact, we present a quantum computing algorithm that defines an invariant over Graph Isomorphism characterisation. This quantum algorithm is able to distinguish more non-isomorphic graphs than most of the known invariants so far. The proof of correctness and some hints illustrating the extent and reason of the improvement are also included in this paper.

In this paper we investigate the effects of a quantum algorithm which increases the amplitude of the states corresponding to the solutions of the partition problem by a factor of almost two. The study is limited to one iteration.