# A Simple Quantum Blockmodeling with Qubits and Permutations

arXiv: https://arxiv.org/abs/2311.07726 · HTML: https://mlsanity.com/paper/2311.07726/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 45 references that are in the map.
- First posted on arXiv 13 Nov 2023.

## Builds on (most cited first, 12 of 12)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [QUBO Formulations for Training Machine Learning Models](https://mlsanity.com/paper/2008.02369/) (2020)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [Power and limitations of single-qubit native quantum neural networks](https://mlsanity.com/paper/2205.07848/) (2022)
- [Multilayer stochastic block models reveal the multilayer structure of complex networks](https://mlsanity.com/paper/1411.1098/) (2014)
- [A Simple Quantum Neural Net with a Periodic Activation Function](https://mlsanity.com/paper/1804.07633/) (2018)
- [Scientific co-authorship networks](https://mlsanity.com/paper/1711.00770/) (2017)

## Abstract (arXiv)

Blockmodeling of a given problem represented by an N× 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). Although classical matrix permutations can be efficiently done by swapping pointers for the permuted rows (or columns) of the matrix, by changing row-column order, a permutation changes the location of the matrix elements, which determines the membership of a group in the matrix based blockmodeling. Therefore, a brute force initial estimation of a fitness value for a candidate solution involving counting the memberships of the elements may require going through all the sum of the rows (or the columns). Similarly permutations can be also implemented efficiently on quantum computers, e.g. a NOT gate on a qubit. In this paper, using permutation matrices and qubit measurements, we show how to solve blockmodeling on quantum computers. In the model, the measurement outcomes of a small group of qubits are mapped to indicate the fitness value. However, if the number of qubits in the considered group is much less than n=log(N), it is possible to find or update the fitness value based on the state tomography in O(poly(log(N))). Therefore, when the number of iterations is less than log(N) time and the size of the considered qubit group is small, we show that it may be possible to reach the solution very efficiently.