Finding an answer key given tests and scores Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete with all answer choices and their grades (number of questions correct). Find the set of answers keys which produce these scores.

I and a few friends had a go at it, but I was wondering if there was an efficient algorithm to solve this.
Solving this problem is NP-hard. In particular, even deciding whether there exists an answer key consistent with the given answer choices and scores is NP-complete. We can prove this by reduction from 1-in-3 SAT.

Given a 1-in-3 SAT formula with $c$ clauses and $n$ variables, we construct an instance of your problem with $n$ questions, each with 3 choices, and $c+1$ sample answer/grade pairs.

For each variable $x$, one of the questions is "what is the value of boolean variable $x$?" and the three possible answers are "True", "False", and "17".

One student answers every question with the answer $17$ and gets a score of zero. The remaining students are each assigned a clause. For every positive literal $x$ occurring in the clause, the student answers the question about $x$ with the answer "True". For every negative literal $\neg x$ occurring in the clause, the student answers the question about $x$ with the answer "False". For every other question, the student answers $17$. Every such student gets a score of one.

An answer key must correspond with an assignment of binary values to the variables (since no question has $17$ as the correct answer as shown by the fact that the student who always answered $17$ got zero points). Furthermore, there must be exactly one true literal in each clause under this assignment in order for the answer key to match the scores given to the students. In other words, the satisfying assignments to the input 1-in-3 SAT formula are in a bijection with the answer keys consistent with the student scores.

Clearly then, deciding whether an answer key consistent with the student scores exists is NP-hard. Similar arguments can be made to show that for example counting answer keys is #P-complete.