Quantum State Isomorphism
arXiv:1709.09622
Abstract
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.
22 pages, 2 figures
References in corpus (11)
- Improved Simulation of Stabilizer Circuits
- Graph Isomorphism in Quasipolynomial Time
- Quantum NP - A Survey
- The Church of the Symmetric Subspace
- Hardness of approximation for quantum problems
- Two-message quantum interactive proofs are in PSPACE
- Quantum statistical zero-knowledge
- Efficient Inner-product Algorithm for Stabilizer States
- Learning stabilizer states by Bell sampling
- Quantum Arthur-Merlin Games
- Quantum Versus Classical Proofs and Advice