Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?

Question

(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public.

• For example, questions about $\mathrm{P}$ vs. $\mathrm{NP}$ can easily be cast in an accessible manner by talking about Sudoku, or the traveling salesperson problem, etc.

• Similarly questions about the polynomial hierarchy $\mathrm{PH}$ can be instantiated as questions about games, such as "is there a mate-in-$n$ strategy for white?"

Many open problems in QCS, at least initially, seem to require a good deal of a-priori knowledge to even begin to understand the questions being asked.

For example, even describing the initial rush to find $\mathrm{BQP}$ solutions to instances of the hidden-subgroup (HSP) problem seemed to expect the audience to not only have a good deal of knowledge of, or respect for, QM, but also a small amount of knowledge of (finite) group theory.

EDIT Upon further review I think this is an unfair dunk on the early researchers looking in to HSP solutions. Researches looked into the HSP precisely because HSP generalized a lot of problems that people cared about. /EDIT

I think the subject has matured so much from the mid-90's that I think there are some important outstanding problems that can be described quickly, to a wider audience. The descriptions might not demand much but a little patience and curiosity of the audience.

I'm looking for a kind of "big-list" of such accessible open problems. This may be helpful for perennial questions like "what's a good research topic for me?"

For example, some open problems that come to mind include:

• What can be said about whether graph isomorphism $\mathsf{GI}$ is in $\mathrm{BQP}$? Is it even a worthwhile question in light of Babai's breakthrough? I think this can be described to a curious-enough audience
• Can a quantum computer distinguish various knots? I think the problem statement can be described to maybe even patient elementary-school students
• One of my favorite problems is the "beltway problem" - determining the location of exits along a beltway (highway around a city) given only their inter-exit distances. This is related to Golomb rulers. I like to think about whether this is in $\mathrm{BQP}$
• The existence of $\mathrm{QMA}$ certificates does not always seem to imply the existence of a $\mathrm{BQP}$ solution, but asking if there's a $\mathrm{QMA}$ certificate for problems that aren't even known to be in $\mathrm{NP}$ seems interesting, such as the $\mathrm{coNP}$ versions of some $\mathrm{NP}$ problems. If framed correctly, these might fit the bill.

Can a list of 'high-concept' open problems in Quantum Computing research be created?

Here, to keep the question narrow enough, by "high-concept" I mean:

• In order to understand the phrasing of the question, a school child might be able to understand at least the question being asked.

I would argue that "Can a quantum computer solve my problem $X$ faster than other regular computers?" is an accessible way to frame the question. Here $X$ is the problem that is accessible (Sudoku/TSP/mate-in-$n$ problems classically).

Answer 1

CW from Self-Answer

I asked this question a while ago, and I've learned I think a little bit about many of the outstanding open problems in the field, and more about science communication in general.

Of course I suspect generally most in the QC community want to have the problems that they work on be accessible to a broader audience. And there are, from my perspective, fantastic science communicators who make that effort to translate problems into a more accessible manner.

The audience of, for example, Quanta Magazine, may not be school children as in the question, but Quanta's done yeoman's work to explain many outstanding problems, and solutions to many of these problems, in the field.

There are also some YouTube videos that target even school-children; see, here.

Aaronson's list of "Ten Semi-Grand Challenges" here meets many desirables inherent in the question; although I doubt a school child could understand many of the questions as framed, they very well could be reframed to be accessible.