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

(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.

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).