Tag Archives: probability

Illustration by Michael S. Helfenbein

Yale physicists find a new form of quantum friction


Physicists at Yale University have observed a new form of quantum friction that could serve as a basis for robust information storage in quantum computers in the future. The researchers are building upon decades of research, experimentally demonstrating a procedure theorized nearly 30 years ago.

The results appear in the journal Science and are based on work in the lab of Michel Devoret, the F.W. Beinecke Professor of Applied Physics.

Quantum computers, a technology still in development, would rely on the laws of quantum mechanics to solve certain problems exponentially faster than classical computers. They would store information in quantum systems, such as the spin of an electron or the energy levels of an artificial atom. Called “qubits,” these storage units are the quantum equivalent of classical “bits.” But while bits can be in states like 0 or 1, qubits can simultaneously be in the 0 and 1 state. This property is called quantum superposition; it is a powerful resource, but also very fragile. Ensuring the integrity of quantum information is a major challenge of the field.

 Illustration by Michael S. Helfenbein
Illustration by Michael S. Helfenbein

Zaki Leghtas, first author on the paper and a postdoctoral researcher at Yale, offered the following metaphor to explain this new form of quantum friction:

Imagine a hill surrounded by two basins. If you put a ball at the top of the hill, it will roll down the sides and settle in one of the basins. As it rolls, it loses energy due to the friction between the ball and the ground, and it slows down. This is why it stops at the bottom of the basin. But friction also causes the ball to leave a path in its wake. By looking at either side of the hill and seeing where grass is flattened and stones are pushed aside, you can tell whether the ball rolled into the right or left basin.

This figure depicts the position of a quantum particle over a time of 19 micro-seconds. Dark colors indicate high probability of the particle existing at the specified position. It is a plot of the time-evolution of the Winger function W (⍺) of the quantum system, with black corresponding to 1.0, white to 0, and blue to –0.05.
This figure depicts the position of a quantum particle over a time of 19 micro-seconds. Dark colors indicate high probability of the particle existing at the specified position. It is a plot of the time-evolution of the Winger function W (⍺) of the quantum system, with black corresponding to 1.0, white to 0, and blue to –0.05.

If you replace the ball with a quantum particle, however, you run into a problem. Quantum particles can exist in many states at the same time, so in theory, the particle could occupy both basins simultaneously. But as the particle is rolling down, the friction between the particle and the hill leaves an impact on the environment, which can be measured. The same friction that stops the particle at the bottom also carves the path. This destroys the superposition and forces the particle to exist in only one basin.

Previously, researchers had been able to take advantage of this friction to trap quantum particles in particular basins. But now, Devoret’s lab demonstrates a new type of friction — one that slows the particle as it rolls, but does not carve a path that tells which side it is choosing. This allows the particle to simultaneously exist in both the left and right basins at the same time.

Each of these “basin” states is both stable and steady. While the quantum particle might move around in the basins, small perturbations won’t kick it out of the basins. Furthermore, any superpositions of these two basin states are also stable and steady. This means they could be used as a basis for storing quantum information.

Technically, this is called a two-dimensional quantum steady-state manifold. Devoret and Leghtas point out that the next step is expanding this two-dimensional manifold to four dimensions — adding two more basins to the landscape. This will allow scientists to redundantly encode quantum information and to do error correction within the manifold. Error correction is one of the key components that must be developed in order to make a practical quantum computer feasible.

Additional authors are Steven Touzard, Ioan Pop, Angela Kou, Brian Vlastakis, Andrei Petrenko, Katrina Sliwa, Anirudh Narla, Shyam Shankar, Michael Hatridge, Matthew Reagor, Luigi Frunzio, Robert Schoelkopf, and Mazyar Mirrahimi of Yale. Mirrahimi also has an appointment at the Institut National de Recherche en Informatique et en Automatique Paris-Rocquencourt.

(Main illustration by Michael S. Helfenbein)

Source: Yale News

Software that knows the risks

Planning algorithms evaluate probability of success, suggest low-risk alternatives.

By Larry Hardesty


CAMBRIDGE, Mass. – Imagine that you could tell your phone that you want to drive from your house in Boston to a hotel in upstate New York, that you want to stop for lunch at an Applebee’s at about 12:30, and that you don’t want the trip to take more than four hours. Then imagine that your phone tells you that you have only a 66 percent chance of meeting those criteria — but that if you can wait until 1:00 for lunch, or if you’re willing to eat at TGI Friday’s instead, it can get that probability up to 99 percent.

That kind of application is the goal of Brian Williams’ group at MIT’s Computer Science and Artificial Intelligence Laboratory — although the same underlying framework has led to software that both NASA and the Woods Hole Oceanographic Institution have used to plan missions.

At the annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) this month, researchers in Williams’ group will present algorithms that represent significant steps toward what Williams describes as “a better Siri” — the user-assistance application found in Apple products. But they would be just as useful for any planning task — say, scheduling flights or bus routes.

Together with Williams, Peng Yu and Cheng Fang, who are graduate students in MIT’s Department of Aeronautics and Astronautics, have developed software that allows a planner to specify constraints — say, buses along a certain route should reach their destination at 10-minute intervals — and reliability thresholds, such as that the buses should be on time at least 90 percent of the time. Then, on the basis of probabilistic models — which reveal data such as that travel time along this mile of road fluctuates between two and 10 minutes — the system determines whether a solution exists: For example, perhaps the buses’ departures should be staggered by six minutes at some times of day, 12 minutes at others.

If, however, a solution doesn’t exist, the software doesn’t give up. Instead, it suggests ways in which the planner might relax the problem constraints: Could the buses reach their destinations at 12-minute intervals? If the planner rejects the proposed amendment, the software offers an alternative: Could you add a bus to the route?

Short tails

One aspect of the software that distinguishes it from previous planning systems is that it assesses risk. “It’s always hard working directly with probabilities, because they always add complexity to your computations,” Fang says. “So we added this idea of risk allocation. We say, ‘What’s your budget of risk for this entire mission? Let’s divide that up and use it as a resource.’”

The time it takes to traverse any mile of a bus route, for instance, can be represented by a probability distribution — a bell curve, plotting time against probability. Keeping track of all those probabilities and compounding them for every mile of the route would yield a huge computation. But if the system knows in advance that the planner can tolerate a certain amount of failure, it can, in effect, assign that failure to the lowest-probability outcomes in the distributions, lopping off their tails. That makes them much easier to deal with mathematically.

At AAAI, Williams and another of his students, Andrew Wang, have a paper describing how to evaluate those assignments efficiently, in order to find quick solutions to soluble planning problems. But the paper with Yu and Fang — which appears at the same conference session — concentrates on identifying those constraints that prevent a problem’s solution.

There’s the rub

Both procedures are rooted in graph theory. In this context, a graph is a data representation that consists of nodes, usually depicted as circles, and edges, usually depicted as line segments connecting the nodes. Any scheduling problem can be represented as a graph. Nodes represent events, and the edges indicate the sequence in which events must occur. Each edge also has an associated weight, indicating the cost of progressing from one event to the next — the time it takes a bus to travel between stops, for instance.

Yu, Williams, and Fang’s algorithm first represents a problem as a graph, then begins adding edges that represent the constraints imposed by the planner. If the problem is soluble, the weights of the edges representing constraints will everywhere be greater than the weights representing the costs of transitions between events. Existing algorithms, however, can quickly home in on loops in the graph where the weights are imbalanced. The MIT researchers’ system then calculates the lowest-cost way of rebalancing the loop, which it presents to the planner as a modification of the problem’s initial constraints.

Source: MIT News Office

Recommendation theory

Model for evaluating product-recommendation algorithms suggests that trial and error get it right.

By Larry Hardesty

Devavrat Shah’s group at MIT’s Laboratory for Information and Decision Systems (LIDS) specializes in analyzing how social networks process information. In 2012, the group demonstrated algorithms that could predict what topics would trend on Twitter up to five hours in advance; this year, they used the same framework to predict fluctuations in the prices of the online currency known as Bitcoin.

Next month, at the Conference on Neural Information Processing Systems, they’ll present a paper that applies their model to the recommendation engines that are familiar from websites like Amazon and Netflix — with surprising results.

“Our interest was, we have a nice model for understanding data-processing from social data,” says Shah, the Jamieson Associate Professor of Electrical Engineering and Computer Science. “It makes sense in terms of how people make decisions, exhibit preferences, or take actions. So let’s go and exploit it and design a better, simple, basic recommendation algorithm, and it will be something very different. But it turns out that under that model, the standard recommendation algorithm is the right thing to do.”

The standard algorithm is known as “collaborative filtering.” To get a sense of how it works, imagine a movie-streaming service that lets users rate movies they’ve seen. To generate recommendations specific to you, the algorithm would first assign the other users similarity scores based on the degree to which their ratings overlap with yours. Then, to predict your response to a particular movie, it would aggregate the ratings the movie received from other users, weighted according to similarity scores.

To simplify their analysis, Shah and his collaborators — Guy Bresler, a postdoc in LIDS, and George Chen, a graduate student in MIT’s Department of Electrical Engineering and Computer Science (EECS) who is co-advised by Shah and EECS associate professor Polina Golland — assumed that the ratings system had two values, thumbs-up or thumbs-down. The taste of every user could thus be described, with perfect accuracy, by a string of ones and zeroes, where the position in the string corresponds to a particular movie and the number at that location indicates the rating.

Birds of a feather

The MIT researchers’ model assumes that large groups of such strings can be clustered together, and that those clusters can be described probabilistically. Rather than ones and zeroes at each location in the string, a probabilistic cluster model would feature probabilities: an 80 percent chance that the members of the cluster will like movie “A,” a 20 percent chance that they’ll like movie “B,” and so on.

The question is how many such clusters are required to characterize a population. If half the people who like “Die Hard” also like “Shakespeare in Love,” but the other half hate it, then ideally, you’d like to split “Die Hard” fans into two clusters. Otherwise, you’d lose correlations between their preferences that could be predictively useful. On the other hand, the more clusters you have, the more ratings you need to determine which of them a given user belongs to. Reliable prediction from limited data becomes impossible.

In their new paper, the MIT researchers show that so long as the number of clusters required to describe the variation in a population is low, collaborative filtering yields nearly optimal predictions. But in practice, how low is that number?

To answer that question, the researchers examined data on 10 million users of a movie-streaming site and identified 200 who had rated the same 500 movies. They found that, in fact, just five clusters — five probabilistic models — were enough to account for most of the variation in the population.

Missing links

While the researchers’ model corroborates the effectiveness of collaborative filtering, it also suggests ways to improve it. In general, the more information a collaborative-filtering algorithm has about users’ preferences, the more accurate its predictions will be. But not all additional information is created equal. If a user likes “The Godfather,” the information that he also likes “The Godfather: Part II” will probably have less predictive power than the information that he also likes “The Notebook.”

Using their analytic framework, the LIDS researchers show how to select a small number of products that carry a disproportionate amount of information about users’ tastes. If the service provider recommended those products to all its customers, then, based on the resulting ratings, it could much more efficiently sort them into probability clusters, which should improve the quality of its recommendations.

Sujay Sanghavi, an associate professor of electrical and computer engineering at the University of Texas at Austin, considers this the most interesting aspect of the research. “If you do some kind of collaborative filtering, two things are happening,” he says. “I’m getting value from it as a user, but other people are getting value, too. Potentially, there is a trade-off between these things. If there’s a popular movie, you can easily show that I’ll like it, but it won’t improve the recommendations for other people.”

That trade-off, Sanghavi says, “has been looked at in an empirical context, but there’s been nothing that’s principled. To me, what is appealing about this paper is that they have a principled look at this issue, which no other work has done. They’ve found a new kind of problem. They are looking at a new issue.”

Source : MIT News