Quantum Algorithms for Tree Isomorphism and State Symmetrization

Details Quantum Algorithms for Tree Isomorphism and State Symmetrization Quantum Algorithms for Tree Isomorphism and State Symmetrization

2010-11-18

arxiv.org/abs/1011.4138v3

Physics

Quantum Physics

Scientific paper

The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithms for Tree Isomorphism and State Symmetrization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Algorithms for Tree Isomorphism and State Symmetrization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms for Tree Isomorphism and State Symmetrization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-536420