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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.