Posted on **07/31/2012 11:57:26 AM PDT** by **LibWhacker**

**Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.**

Interactive proofs, which MIT researchers helped pioneer, have emerged as one of the major research topics in theoretical computer science. In the classic interactive proof, a questioner with limited computational power tries to extract reliable information from a computationally powerful but unreliable respondent. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they’re just as important for the insight they provide into the complexity of computational problems.

Twenty years ago, researchers showed that if the questioner in an interactive proof is able to query multiple omniscient respondents — which are unable to communicate with each other — it can extract information much more efficiently than it could from a single respondent. As quantum computing became a more popular research topic, however, computer scientists began to wonder whether such multiple-respondent — or “multiprover” — systems would still work if the respondents were able to perform measurements on physical particles that were “entangled,” meaning that their quantum properties were dependent on each other.

At the IEEE Symposium on Foundations of Computer Science in October, Thomas Vidick, a postdoc at MIT’s Computer Science and Artificial Intelligence Laboratory, and Tsuyoshi Ito, a researcher at NEC Labs in Princeton, N.J., finally answer that question: Yes, there are multiprover interactive proofs that hold up against entangled respondents. That answer is good news for cryptographers, but it’s bad news for quantum physicists, because it proves that there’s no easy way to devise experiments that illustrate the differences between classical and quantum physical systems.

It’s also something of a surprise, because when the question was first posed, it was immediately clear that some multiprover proofs were not resilient against entanglement. Vidick and Ito didn’t devise the proof whose resilience they prove, but they did develop new tools for analyzing it.

**Boxed in**

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.

The proof that Vidick and Ito analyzed is designed to make cheating difficult by disguising the questioner’s intent. To get a sense of how it works, imagine a graph that in some sense plots questions against answers, and suppose that the questioner is interested in two answers, which would be depicted on the graph as two points. Instead of asking the two questions of interest, however, the questioner asks at least three different questions. If the answers to those questions fall on a single line, then so do the answers that the questioner really cares about, which can now be calculated. If the answers don’t fall on a line, then at least one of the respondents is trying to cheat.

“That’s basically the idea, except that you do it in a much more high-dimensional way,” Vidick says. “Instead of having two dimensions, you have ‘N’ dimensions, and you think of all the questions and answers as being a small, N-dimensional cube.”

**Gaining perspective**

This type of proof turns out to be immune to quantum entanglement. But demonstrating that required Vidick and Ito to develop a new analytic framework for multiprover proofs.

According to the weird rules of quantum mechanics, until a measurement is performed on a quantum particle, the property being measured has no definite value; measuring snaps the particle into a definite state, but that state is drawn randomly from a probability distribution of possible states.

The problem is that, when particles are entangled, their probability distributions can’t be treated separately: They’re really part of a single big distribution. But any mathematical description of that distribution supposes a bird’s-eye perspective that no respondent in a multiprover proof would have. Finding a way to do justice to both the connection between the measurements and the separation of the measurers proved enormously difficult. “It took Tsuyoshi and me about a year and a half,” Vidick says. “But in fact, one could say I’ve been working on this since 2006. My very first paper was on exactly the same topic.”

Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito’s paper is the quantum analogue of an earlier paper on multiprover interactive proofs that “basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years.” Similarly, she says, the new paper “could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory.”

The paper could also have implications for physics, Aharonov adds. “This is a step toward deepening our understanding of the notion of entanglement, and of things that happen in quantum systems — correlations in quantum systems, and efficient descriptions of quantum systems, et cetera,” she says. “But it’s very indirect. This looks like an important step, but it’s a long journey.”

If you're flummoxed by this, you're not alone!

To: **LibWhacker**

To: **LibWhacker**

3
posted on **07/31/2012 12:06:46 PM PDT**
by Gay State Conservative
(Poor Barack.If He's Reelected,Think Of The Mess He'll Inherit!)

To: **LibWhacker**

I just read the whole thing. Not only am I now dumber than when I started, it hurt, too. -Wb

To: **LibWhacker**

"10-year-old problem in theoretical computer science falls"

**Well ? Don't just stand there, help the little fella up !**

5
posted on **07/31/2012 12:11:12 PM PDT**
by fieldmarshaldj
(If you like lying Socialist dirtbags, you'll love Slick Willard)

To: **LibWhacker**

Whew!

I’ll sleep much better now....

This has had me concerned for some time!

6
posted on **07/31/2012 12:11:46 PM PDT**
by G Larry
(Progressives are Regressive because their objectives devolve to the lowest common denominator.)

To: **LibWhacker**

I always thought an “interactive proof” was the hangover you got from mixing your drinks the night before.....

7
posted on **07/31/2012 12:15:01 PM PDT**
by G Larry
(Progressives are Regressive because their objectives devolve to the lowest common denominator.)

To: **LibWhacker**

So, how do you find an unentangled particle if they are undefined to start with and the possibility of an entanglement is also unknown. All particles are interacting, and therefore entangled.

Or in otherwords, when talking Quantam Physics, vs Physics, is the same as Political Correctness vs just being Correct.

or

Bullshirt in, Bullshirt out.

8
posted on **07/31/2012 12:15:37 PM PDT**
by American in Israel
(A wise man's heart directs him to the right, but the foolish mans heart directs him toward the left.)

To: **American in Israel**

I play a game on my iPhone called “Entanglement”, but it’s much simpler......

To: **LibWhacker**

I’ll run it through my Commodore 63 and TI98 4A.

10
posted on **07/31/2012 12:22:28 PM PDT**
by showme_the_Glory
(ILLEGAL: prohibited by law. ALIEN: Owing political allegiance to another country or government)

To: **American in Israel**

Ummm. the first basic quantum computers have been built.

Entangled has a specific meaning in Quantum physics, vs. Classical physics.

/johnny

To: **LibWhacker**

for later, when I swap brains

To: **LibWhacker**

This is a big step in cryptography. If this can be practically implemented in security appliances, it could prevent DDoS attacks by requiring something akin to modern-day Captchas but by preventing automated attacks vs. attacks by a human or someone/thing that could attempt to subvert the cryptography.

For instance, modern day captchas use numbers and letters with random colors, pictures, etc. in the frame. This sort of cryptography would require plotting against questions that have yet to be asked, and that sort of thing could be required in multi-factor authentication schemes for computer logins, access to facilities, and the like.

It essentially invalidates guessing or “cheating” by pre-formulation of answers utilizing questions that aren’t yet put forward but could be guessed if the respondent already knew.

Okay, now my brain hurts.

To: **dirtboy**

—According to the weird rules of quantum mechanics, until a measurement is performed on a quantum particle, the property being measured has no definite value; measuring snaps the particle into a definite state, but that state is drawn randomly from a probability distribution of possible states.—

And then someone shows up in a ship powered by the infinite improbability drive and messes the whole thing up.

To: **LibWhacker**

well. duh.

To: **showme_the_Glory**

Lucky. I'm stuck with a VIC-19 and an Atari 399.

16
posted on **07/31/2012 1:58:04 PM PDT**
by Dr. Sivana
("I love to hear you talk talk talk, but I hate what I hear you say."-Del Shannon)

To: **LibWhacker**

I am a computer geek. I love computers. They have been the wellspring of my livelihood for decades. I hold many, many computer related certifications, and I really know my stuff.

This made no sense to me at all!

17
posted on **07/31/2012 4:26:26 PM PDT**
by America_Right
(Remember, Republicans have a lot more in common with Democrats than they do with Tea Partiers.)

To: **America_Right**

This made no sense to me at all!

I'm not alone then.

18
posted on **07/31/2012 6:10:29 PM PDT**
by OneWingedShark
(Q: Why am I here? A: To do Justly, to love mercy, and to walk humbly with my God.)

**Disclaimer:**
Opinions posted on Free Republic are those of the individual
posters and do not necessarily represent the opinion of Free Republic or its
management. All materials posted herein are protected by copyright law and the
exemption for fair use of copyrighted works.

FreeRepublic.com is powered by software copyright 2000-2008 John Robinson