This work is an exploration of how graphs and permutations can be applied in the context of quantum information processing. In Chapter 2 we consider problems about the permutations of the subsystems of a quantum system. Explicitly, we attempt to understand the problem of determining if two quantum states of N qubits are isomorphic: if one can be obtained from the other by permuting its subsystems. We show that the well known graph isomorphism problem is a special case of state isomorphism. We also show that the complement of state isomorphism, the problem of determining if two states are not isomorphic, can be verified by a quantum interactive proof system, and that this proof system can be made statistical zero knowledge. We also consider the complexity of isomorphism problems for stabilizer states, and mixed states. In Chapter 3 we work with a special class of quantum states called grid states, in an effort to develop a toy model for mixed state entanglement. The key idea with grid states is that they can be represented by what we call a grid-labelled graph, literally, a graph forced to have vertices on a two dimensional grid. We show that whether or not a grid state is entangled can sometimes be determined solely from the structural properties of its corresponding grid-labelled graph. We use the grid state framework to build families of bound entangled states, suggesting that even in this restricted setting detecting entanglement is non-trivial and will require more than a single entanglement criterion.
We consider a problem we call StateIsomorphism: given two quantum states of n qubits, can one be obtained from the other by rearranging the qubit subsystems? Our main goal is to study the complexity of this problem, which is a natural quantum generalisation of the problem StringIsomorphism. We show that StateIsomorphism is at least as hard as GraphIsomorphism, and show that these problems have a similar structure by presenting evidence to suggest that StateIsomorphism is an intermediate problem for QCMA. In particular, we show that the complement of the problem, StateNonIsomorphism, has a two message quantum interactive proof system, and that this proof system can be made statistical zero-knowledge. We consider also StabilizerStateIsomorphism (SSI) and MixedStateIsomorphism (MSI), showing that the complement of SSI has a quantum interactive proof system that uses classical communication only, and that MSI is QSZK-hard.
The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph
G1 that transforms
G1 to another given graph
G2 and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.
Graph-theoretic structures play a central role in the description and analysis of quantum systems. In this work, we introduce a new class of quantum states, called
Aα-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix
D and the adjacency matrix
AG of a graph
G. The constructed states are different from the standard graph states arising from stabiliser formalism. Our approach is also different from the approach used by Braunstein et al. This class of states depend on a tunable mixing parameter
α∈(0,1]. We first establish the conditions under which the associated operator
ραAG is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for
Aα-graph states in terms of graph parameters. This PPT condition involves only the Frobenius norm of the adjacency matrix of the graph, the degrees of the vertices and the total number of vertices. For simple graphs, we obtain the range of the parameter
α for which the
Aα-graph states represent a class of entangled states. We then develop a graph-theoretic formulation of a moments-based entanglement detection criterion, focusing on the recently proposed
p3-PPT criterion, which relies on the second and third moments of the partial transposition. Since the estimation of these moments is experimentally accessible via randomised measurements, swap operations, and machine-learning-based protocols, our approach provides a physically relevant framework for detecting entanglement in structured quantum states derived from graphs. This work bridges graph theory and moments-based entanglement detection, offering a new perspective on the role of combinatorial structures in quantum correlations.
Using the signed Laplacian matrix, and weighted and hybrid graphs, we present additional ways to interpret graphs as grid states. Hybrid graphs offer the most general interpretation. Existing graphical methods that characterize entanglement properties of grid states are adapted to these interpretations. These additional classes of grid states are shown to exhibit rich entanglement properties, including bound entanglement. Further, we introduce graphical techniques to construct bound-entangled states in a modular fashion. We also extend the grid states model to hypergraphs. Our work, on one hand, opens up possibilities for constructing additional families of mixed quantum states in the grid state model. On the other hand, it can serve as an instrument for investigating entanglement problems from a graph theory perspective.
Grid states form a discrete set of mixed quantum states that can be described by graphs. We characterize the entanglement properties of these states and provide methods to evaluate entanglement criteria for grid states in a graphical way. With these ideas we find bound entangled grid states for two-particle systems of any dimension and multiparticle grid states that provide examples for the different aspects of genuine multiparticle entanglement. Our findings suggest that entanglement theory for grid states, although being a discrete set, has already a complexity similar to that for general states.
This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.