PRESS-NEWS.org - Press Release Distribution
PRESS RELEASES DISTRIBUTION

MIT News Release: 10-year-old problem in theoretical computer science falls

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

2012-07-30
(Press-News.org) CAMBRIDGE, Mass. -- 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.

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

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

### Written by Larry Hardesty, MIT News Office


ELSE PRESS RELEASES FROM THIS DATE:

When rules change, brain falters

When rules change, brain falters
2012-07-30
EAST LANSING, Mich. — For the human brain, learning a new task when rules change can be a surprisingly difficult process marred by repeated mistakes, according to a new study by Michigan State University psychology researchers. Imagine traveling to Ireland and suddenly having to drive on the left side of the road. The brain, trained for right-side driving, becomes overburdened trying to suppress the old rules while simultaneously focusing on the new rules, said Hans Schroder, primary researcher on the study. "There's so much conflict in your brain," said Schroder, "that ...

Gene mutations linked to most cases of rare disorder -- Alternating Hemoplegia of Childhood

2012-07-30
(SALT LAKE CITY)—Alternating hemiplegia of childhood (AHC) is a rare disorder that usually begins in infancy, with intermittent episodes of paralysis and stiffness, first affecting one side of the body, then the other. Symptoms mysteriously appear and disappear, again and again, and affected children often experience dozens of episodes per week. As they get older, children fall progressively behind their peers in both intellectual abilities and motor skills, and more than half develop epilepsy. Unfortunately, medications that work for epilepsy have been unsuccessful in ...

Smell the potassium

Smell the potassium
2012-07-30
Kansas City, Missouri - The vomeronasal organ (VNO) is one of evolution's most direct enforcers. From its niche within the nose in most land-based vertebrates, it detects pheromones and triggers corresponding basic-instinct behaviors, from compulsive mating to male-on-male death matches. A new study from the Stowers Institute for Medical Research, published online in Nature Neuroscience on July 29, 2012, extends the scientific understanding of how pheromones activate the VNO, and has implications for sensory transduction experiments in other fields. "We found two new ...

Cutting the graphene cake

2012-07-30
Sandwiching individual graphene sheets between insulating layers in order to produce electrical devices with unique new properties, the method could open up a new dimension of physics research. Writing in Nature Materials, the scientists show that a new side-view imaging technique can be used to visualize the individual atomic layers of graphene within the devices they have built. They found that the structures were almost perfect even when more than 10 different layers were used to build the stack. This surprising result indicates that the latest techniques of isolating ...

Cell receptor has proclivity for T helper 9 cells, airway inflammation

2012-07-30
BOSTON, MA—A research team led by Xian Chang Li, MD, PhD, Brigham and Women's Hospital (BWH) Transplantation Research Center, has shed light on how a population of lymphocytes, called CD4+ T cells, mature into various subsets of adult T helper cells. In particular, the team uncovered that a particular cell surface molecule, known as OX40, is a powerful inducer of new T helper cells that make copious amounts of interleukin-9 (IL-9) (and therefore called TH9 cells) in vitro; such TH9 cells are responsible for ongoing inflammation in the airways in the lungs in vivo. The ...

Massachusetts Eye and Ear researchers discover elusive gene that causes a form of blindness from birth

2012-07-30
BOSTON (July 29, 2012) – Researchers from the Massachusetts Eye and Ear Infirmary, The Children's Hospital of Philadelphia, Loyola University Chicago Health Sciences Division and their collaborators have isolated an elusive human gene that causes a common form of Leber congenital amaurosis (LCA), a relatively rare but devastating form of early-onset blindness. The new LCA gene is called NMNAT1. Finding the specific gene mutated in patients with LCA is the first step towards developing sight-saving gene therapy. LCA is an inherited retinal degenerative disease characterized ...

New discovery of how carbon is stored in the Southern Ocean

2012-07-30
A team of British and Australian scientists has discovered an important method of how carbon is drawn down from the surface of the Southern Ocean to the deep waters beneath. The Southern Ocean is an important carbon sink in the world – around 40% of the annual global CO2 emissions absorbed by the world's oceans enter through this region. Reporting this week in the journal Nature Geoscience, scientists from British Antarctic Survey (BAS) and Australia's national research agency, the Commonwealth Scientific and Industrial Research Organisation (CSIRO), reveal that rather ...

Gene discovery set to help with mysterious paralysis of childhood

2012-07-30
DURHAM, N.C. – Alternating hemiplegia of childhood (AHC) is a very rare disorder that causes paralysis that freezes one side of the body and then the other in devastating bouts that arise at unpredictable intervals. Seizures, learning disabilities and difficulty walking are common among patients with this diagnosis. Researchers at Duke University Medical Center have now discovered that mutations in one gene cause the disease in the majority of patients with a diagnosis of AHC, and because of the root problem they discovered, a treatment may become possible. The study ...

Giant ice avalanches on Iapetus provide clue to extreme slippage elsewhere in the solar system

Giant ice avalanches on Iapetus provide clue to extreme slippage elsewhere in the solar system
2012-07-30
"We see landslides everywhere in the solar system," says Kelsi Singer, graduate student in earth and planetary sciences in Arts & Sciences at Washington University in St. Louis, "but Saturn's icy moon Iapetus has more giant landslides than any body other than Mars." The reason, says William McKinnon, PhD, professor of earth and planetary sciences, is Iapetus' spectacular topography. "Not only is the moon out-of-round, but the giant impact basins are very deep, and there's this great mountain ridge that's 20 kilometers (12 miles) high, far higher than Mount Everest. "So ...

Magnetic field, mantle convection and tectonics

2012-07-30
On a time scale of tens to hundreds of millions of years, the geomagnetic field may be influenced by currents in the mantle. The frequent polarity reversals of Earth's magnetic field can also be connected with processes in the mantle. These are the research results presented by a group of geoscientists in the new advance edition of "Nature Geoscience" on Sunday, July 29th. The results show how the rapid processes in the outer core, which flows at rates of up to about one millimeter per second, are coupled with the processes in the mantle, which occur more in the velocity ...

LAST 30 PRESS RELEASES:

Pennington Biomedical’s Dr. Leanne Redman honored with the E. V. McCollum Award from the American Society for Nutrition

CCNY physicists uncover electronic interactions mediated via spin waves

Researchers’ 3D-printing formula may transform future of foam

Nurture more important than nature for robotic hand

Drug-delivering aptamers target leukemia stem cells for one-two knockout punch

New study finds that over 95% of sponsored influencer posts on Twitter were not disclosed

New sea grant report helps great lakes fish farmers navigate aquaculture regulations

Strain “trick” improves perovskite solar cells’ efficiency

How GPS helps older drivers stay on the roads

Estrogen and progesterone stimulate the body to make opioids

Dancing with the cells – how acoustically levitating a diamond led to a breakthrough in biotech automation

Machine learning helps construct an evolutionary timeline of bacteria

Cellular regulator of mRNA vaccine revealed... offering new therapeutic options

Animal behavioral diversity at risk in the face of declining biodiversity

Finding their way: GPS ignites independence in older adult drivers

Antibiotic resistance among key bacterial species plateaus over time

‘Some insects are declining but what’s happening to the other 99%?’

Powerful new software platform could reshape biomedical research by making data analysis more accessible

Revealing capillaries and cells in living organs with ultrasound

American College of Physicians awards $260,000 in grants to address equity challenges in obesity care

Researchers from MARE ULisboa discover that the European catfish, an invasive species in Portugal, has a prolonged breeding season, enhancing its invasive potential

Rakesh K. Jain, PhD, FAACR, honored with the 2025 AACR Award for Lifetime Achievement in Cancer Research

Solar cells made of moon dust could power future space exploration

Deporting immigrants may further shrink the health care workforce

Border region emergency medical services in migrant emergency care

Resident physician intentions regarding unionization

Healthy nutrition and physical lifestyle choices lower cancer mortality risk for survivors, new ACS study finds

Mass General Brigham researchers reveal 17 modifiable risk factors shared by stroke, dementia, and late-life depression

Promising drug discovery research gets funding boost from Ontario Institute for Cancer Research

Carbon capture could become practical with scalable, affordable materials

[Press-News.org] MIT News Release: 10-year-old problem in theoretical computer science falls
Interactive proofs -- mathematical games that underlie much modern cryptography -- work even if players try to use quantum information to cheat