A quantum solution to an old problem.
Image: Jeff Kubina/Flickr
Decision making is among the more natural tasks for an algorithm. For one thing, it's a way of cutting through all of the bullshit biases, faulty memories, and emotional noise of human brains; the archetypal two-columns-on-scratch-paper, pros vs. cons process of choosing could be considered an algorithm, but as things get more computational, decision-making algorithms get complex fast.
A number of formal decision-making algorithms (or algorithms that can aid in decision-making) depend on probabilistic reasoning. One particular group is helpful in problems involving the so-called exploration-exploitation dilemma, which is essentially an optimization problem that attempts to balance the costs of acquiring new information with those of using existing knowledge ("free" information). A decision maker can explore some outcome a number of times, formulating a better and better probabilistic estimate of that outcome occurring given an actual decision, but that requires time and effort, yielding better guesses but still never total certainties.
"Our results imply that efficient decision-making based on single photons could become a reality in the future"
Included in this collection are a lot of kind of difficult computations, including the Tug-of-War, softmax, and upper confidence bounds algorithms. Probability is messy in algorithms, generally, but information researchers at the Néel Institute in Grenoble and the National Institute of Information and Communications Technology in Tokyo have devised an unlikely alternative: using the probabilistic nature of quantum particles to aid in computational decision-making.
The group's work is described in a recent issue of the journal Scientific Reports. "The present study aims to physically implement decision making using the intrinsic quantum attributes of single photons," they write. "The need to make accurate decisions in uncertain, dynamically changing environments appears in all aspects of life. Which stock should I buy? Which option should I take in the next move in a board or electronic game?"
The classic illustration of exploration-exploitation is the multi-armed bandit problem. A gambler is presented with a row of slot machines (which are sometimes referred to as "one-arm bandits") and given the task of choosing which machines to play, how often to play them, and what order to play them in. Every time the gambler pulls a machine's lever, they receive a random reward according to a probabilistic distribution inherent to that machine. The dilemma is of whether to gain new information about the machines (their reward probabilities) or to exploit the information the gambler already has from previous pulls. What will result in the most winnings?
The gambler should maybe just ask some photons. Photons, which are the quantized or particle forms of light, have the property of polarization. They are either polarized vertically or they are polarized horizontally. If we fire some photons at a polarizing beam splitter, we can ensure a 100 percent probability of finding horizontally polarized photons if we use a horizontally oriented filter, or a 100 percent probability of finding vertically polarized photons if we use a vertical filter. This seems obvious, but the weird thing is what happens when the filter is oriented between vertical and horizontal, e.g. at 45 degrees. The result aren't diagonally-polarized photons slipping through, but even odds of vertical and horizontal photons.
To model the bandit problem, the researchers started out with the 45 degree orientation (even odds), and every time a vertical photon registered, the orientation was shifted a bit toward vertical, and vise versa. So, now we just swap horizontal/vertical for machine 1/machine 2. As more photons are fired and more machine handles are pulled, a feedback loop continually refines the problem, ensuring an ideal balance between exploration and exploitation. It's pretty clever.
"Our results imply that efficient decision-making based on single photons could become a reality in the future and potentially impact a wide range of information and communication technologies," co-author Aurélien Drezet tells NanotechWeb. "This is because the 'multi-armed bandit' problem is in fact at the foundation of many important applications, including, for example, frequency assignment in wireless communications and web advertising, to name but two."