The problem of quantum states

Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban +1 more

We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA $\cap$ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP $\cap$ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.

David S. Simon

Galina Nemova

Tobias J. Osborne

The quantum marginal problem asks, given a set of reduced quantum states of a multipartite system, whether there exists a joint quantum state consistent with these reduced states. The quantum marginal problem is known to be hard to solve in general as it is a variant of the N-representability problem. We provide entropic bounds on the number of orthogonal solutions to the quantum marginal problem.

Joel Klassen

The quantum marginal problem asks whether a family of quantum marginals are compatible with a global quantum state. It is of central importance to a wide range of topics in both quantum many body physics and quantum information. Often it can be the case that when a family of quantum marginals are compatible with a global quantum state, that global state is unique. This thesis explores the role of uniqueness in the quantum marginal problem, in particular the distinction between uniqueness among pure states and uniqueness among all states. A particularly important vari- ant of the quantum marginal problem is the symmetric extendibility problem. This thesis makes headway on characterizing the extremal points of a particular class of symmetric extendibility problems, and demonstrates the importance of understand- ing the distinction between being uniquely determined among mixed states and being uniquely determined among pure states in making further progress in this direction.

Harry Paul