We show the application of permutation-invariant quantum circuits to the clique problem. The experiment asks to label a clique through identification of the nodes in a larger subgraph. The permutation-invariant quantum circuit outperforms a cyclic-invariant alternative as well as a standard quantum machine learning ansatz. We explain the behavior through the intrinsic symmetry of the problem, in the sense that the problem is symmetric under permutation of both the feature and the label.
We show the application of permutation-invariant quantum circuits to the clique problem. The experiment asks to label a clique through identification of the nodes in a larger subgraph. The permutation-invariant quantum circuit outperforms a cyclic-invariant alternative as well as a standard quantum machine learning ansatz. We explain the behavior through the intrinsic symmetry of the problem, in the sense that the problem is symmetric under permutation of both the feature and the label.
Many computational problems are unchanged under some symmetry operation. In classical machine learning, this can be reflected with the layer structure of the neural network. In quantum machine learning, the ansatz can be tuned to correspond to the specific symmetry of the problem. We investigate this adaption of the quantum circuit to the problem symmetry on graph classification problems. On random graphs, the quantum machine learning ansatz classifies whether a given random graph is connected, bipartite, contains a Hamiltonian path or cycle, respectively. We find that if the quantum circuit reflects the inherent symmetry of the problem, it vastly outperforms the standard, unsymmetrized ansatzes. Even when the symmetry is only approximative, there is still a significant performance gain over non-symmetrized ansatzes. We show how the symmetry can be included in the quantum circuit in a straightforward constructive method.
Quantum machine learning holds the promise of combining the success of classical machine learning methods with the power of quantum computing, however one of the largest obstacles facing the field is the problem of barren plateaus. Parameterised quantum circuits offer a flexible framework for developing quantum machine learning models, but their practicality is constrained by a trade-off between trainability and classical simulability. In general, circuits that are sufficiently expressive to model complex behaviour often exhibit barren plateaus, where gradients vanish and optimisation fails.
In this work we investigate a compositional approach to mitigate this trade-off by assembling larger quantum models from smaller subcomponents. To ensure trainability of these subcomponents, we describe a framework for constructing group-invariant loss functions, which introduce symmetry-induced inductive bias and lead to improved gradient behaviour and generalisation. In particular, we use this framework to design permutation-equivariant quantum graph neural networks for identifying maximal cliques in graphs. The models we construct exhibit superior training gradients through symmetry-induced bias, and our experiments demonstrate that the trained models generalise to larger, more complex problem instances.
Finally, inspired by Quantum-Informed Recursive Optimisation Algorithms (arXiv:2308.13607), we implement a recursive hybrid quantum-classical heuristic using the learned quantum models to guide a classical search procedure, demonstrating improved inference accuracy and scalability. Together, these results suggest that compositional circuits could be a viable pathway towards scalable quantum learning models that remain challenging to reproduce classically.
The implementation of physical symmetries into problem descriptions allows for the reduction of parameters and computational complexity. We show the integration of the permutation symmetry as the most restrictive discrete symmetry into quantum circuits. The permutation symmetry is the supergroup of all other discrete groups. We identify the permutation with a SWAP operation on the qubits. Based on the extension of the symmetry into the corresponding Lie algebra, quantum circuit element construction is shown via exponentiation. This allows for ready integration of the permutation group symmetry into quantum circuit ansatzes. The scaling of the number of parameters is found to be O(n3), significantly lower than the general case and an indication that symmetry restricts the applicability of quantum computing. We also show how to adapt existing circuits to be invariant under a permutation symmetry by modification.
Abstract Variational quantum algorithms are the leading candidate for advantage on near-term quantum hardware. When training a parametrized quantum circuit in this setting to solve a specific problem, the choice of ansatz is one of the most important factors that determines the trainability and performance of the algorithm. In quantum machine learning (QML), however, the literature on ansatzes that are motivated by the training data structure is scarce. In this work, we introduce an ansatz for learning tasks on weighted graphs that respects an important graph symmetry, namely equivariance under node permutations. We evaluate the performance of this ansatz on a complex learning task, namely neural combinatorial optimization, where a machine learning model is used to learn a heuristic for a combinatorial optimization problem. We analytically and numerically study the performance of our model, and our results strengthen the notion that symmetry-preserving ansatzes are a key to success in QML.
The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .
This paper establishes a framework of quantum clique gossiping by introducing local clique operations to networks of interconnected qubits. Cliques are local structures in complex networks being complete subgraphs, which can be used to accelerate classical gossip algorithms. Based on cyclic permutations, clique gossiping leads to collective multi-party qubit interactions. We show that at reduced states, these cliques have the same acceleration effects as their roles in accelerating classical gossip algorithms. For randomized selection of cliques, such improved rate of convergence is precisely characterized. On the other hand, the rate of convergence at the coherent states of the overall quantum network is proven to be decided by the spectrum of a mean-square error evolution matrix. Remarkably, the use of larger quantum cliques does not necessarily increase the speed of the network density aggregation, suggesting quantum network dynamics is not entirely decided by its classical topology.