A Simple Quantum Blockmodeling with Qubits and Permutations
Ammar Daskin
Blockmodeling of a given problem represented by an $N\times N$ adjacency
matrix can be found by swapping rows and columns of the matrix (i.e.
multiplying matrix from left and right by a permutation matrix). In general,
through performing this task, row and column permutations affect the fitness
value in optimization: For an $N\times N$ matrix, it requires $O(N)$
computations to find (or update) the fitness value of a candidate solution.
  On quantum computers, permutations can be applied in parallel and
efficiently, and their implementations can be as simple as a single qubit
operation (a NOT gate on a qubit) which takes an $O(1)$ time algorithmic step.
In this paper, using permutation matrices, we describe a quantum blockmodeling
for data analysis tasks. In the model, the measurement outcome of a small group
of qubits are mapped to indicate the fitness value. Therefore, we show that it
is possible to find or update the fitness value in $O(log(N))$ time. This lead
us to show that when the number of iterations are less than $log(N)$ time, it
may be possible to reach the same solution exponentially faster on quantum
computers in comparison to classical computers. In addition, since on quantum
circuits the different sequence of permutations can be applied in parallel
(superpositon), the machine learning task in this model can be implemented more
efficiently on quantum computers.