Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLimitations of Quantum Coset States for Graph Isomorphism
85
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Omega(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n, F_{p^m}) and G^n where G is finite and satisfies a suitable property.
rate research
Read More
In the Graph Isomorphism problem two N-vertex graphs G and G are given and the task is to determine whether there exists a permutation of the vertices of G that preserves adjacency and transforms G into G. If yes, then G and G are said to be isomorphic; otherwise they are non-isomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and can also determine all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithms quantum dynamics and show that it correctly: (i) distinguishes non-isomorphic graphs; (ii) recognizes isomorphic graphs; and (iii) finds all automorphisms of a given graph G. We then discuss the GI quantum algorithms experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-Complete Sub-Graph Isomorphism problem.
We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Grobner basis computation. The idea of these algorithms is to encode two graphs into a system of equations that are satisfiable if and only if if the graphs are isomorphic, and then to (try to) decide satisfiability of the system using, for example, the Grobner basis algorithm. In some cases this can be done in polynomial time, in particular, if the equations admit a bounded degree refutation in an algebraic proof systems such as Nullstellensatz or polynomial calculus. We prove linear lower bounds on the polynomial calculus degree over all fields of characteristic different from 2 and also linear lower bounds for the degree of Positivstellensatz calculus derivations. We compare this approach to recently studied linear and semidefinite programming approaches to isomorphism testing, which are known to be related to the combinatorial Weisfeiler-Lehman algorithm. We exactly characterise the power of the Weisfeiler-Lehman algorithm in terms of an algebraic proof system that lies between degree-k Nullstellensatz and degree-k polynomial calculus.
Three new graph invariants are introduced which may be measured from a quantum graph state and form examples of a framework under which other graph invariants can be constructed. Each invariant is based on distinguishing a different number of qubits. This is done by applying alternate measurements to the qubits to be distinguished. The performance of these invariants is evaluated and compared to classical invariants. We verify that the invariants can distinguish all non-isomorphic graphs with 9 or fewer nodes. The invariants have also been applied to `classically hard strongly regular graphs, successfully distinguishing all strongly regular graphs of up to 29 nodes, and preliminarily to weighted graphs. We have found that although it is possible to prepare states with a polynomial number of operations, the average number of preparations required to distinguish non-isomorphic graph states scales exponentially with the number of nodes. We have so far been unable to find operators which reliably compare graphs and reduce the required number of preparations to feasible levels.
Computational advantages gained by quantum algorithms rely largely on the coherence of quantum devices and are generally compromised by decoherence. As an exception, we present a quantum algorithm for graph isomorphism testing whose performance is optimal when operating in the partially coherent regime, as opposed to the extremes of fully coherent or classical regimes. The algorithm builds on continuous-time quantum stochastic walks (QSWs) on graphs and the algorithmic performance is quantified by the distinguishing power (DIP) between non-isomorphic graphs. The QSW explores the entire graph and acquires information about the underlying structure, which is extracted by monitoring stochastic jumps across an auxiliary edge. The resulting counting statistics of stochastic jumps is used to identify the spectrum of the dynamical generator of the QSW, serving as a novel graph invariant, based on which non-isomorphic graphs are distinguished. We provide specific examples of non-isomorphic graphs that are only distinguishable by QSWs in the presence of decoherence.
Graph states are a unique resource for quantum information processing, such as measurement-based quantum computation. Here, we theoretically investigate using continuous-variable graph states for single-parameter quantum metrology, including both phase and displacement sensing. We identified the optimal graph states for the two sensing modalities and showed that Heisenberg scaling of the accuracy for both phase and displacement sensing can be achieved with local homodyne measurements.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
