Interactive proofs are when humans or some theoretical questioner ask a computer questions, and they can’t trust the computer to really understand what they’re getting at. Asking multiple computers different questions makes this style of proofing more efficient. But because quantum physics is weird, mathematicians weren’t sure if different computers would be ignorant of each others’ questions.
In an interactive proof, a questioner asks a series of questions, each of which constrains the range of possible answers to the next question. The questioner doesn’t have the power to compute valid answers itself, but it does have the power to determine whether each new answer meets the constraints imposed by the previous ones. After enough questions, the questioner will either expose a contradiction or reduce the probability that the respondent is cheating to near zero.
Multiprover proofs are so much more efficient than single-respondent proofs because none of the respondents knows the constraints imposed by the others’ answers. Consequently, contradictions are much more likely if any respondent tries to cheat.
But if the respondents have access to particles that are entangled with each other — say, electrons that were orbiting the same atom but were subsequently separated — they can perform measurements — of, say, the spins of select electrons — that will enable them to coordinate their answers. That’s enough to thwart some interactive proofs.
New research shows that there’s a way to do proofs that is immune to quantum entanglement. In other words, if you allow the system to change by introducing the information sharing provided by quantum entanglement, it is still possible to come up with systems that get around that cheating. So don’t worry! Even if we make quantum computers we can still have secured credit cards.