Early on in the study of quantum computers, computer scientists posed a question whose answer, they knew, would reveal something deep about the power of these futuristic machines. Twenty-five years later, it’s been all but solved. In a paper posted online at the end of May, computer scientists Ran Raz and Avishay Tal provide strong evidence that quantum computers possess a computing capacity beyond anything classical computers could ever achieve.

Raz, a professor at Princeton University and the Weizmann Institute of Science, and Tal, a postdoctoral fellow at Stanford University, define a specific kind of computational problem. They prove, with a certain caveat, that quantum computers could handle the problem efficiently while traditional computers would bog down forever trying to solve it. Computer scientists have been looking for such a problem since 1993, when they first defined a class of problems known as “BQP,” which encompasses all problems that quantum computers can solve.

Since then, computer scientists have hoped to contrast BQP with a class of problems known as “PH,” which encompasses all the problems workable by any possible classical computer — even unfathomably advanced ones engineered by some future civilization. Making that contrast depended on finding a problem that could be proven to be in BQP but not in PH. And now, Raz and Tal have done it.

The result does not elevate quantum computers over classical computers in any practical sense. For one, theoretical computer scientists already knew that quantum computers can solve any problems that classical computers can. And engineers are still struggling to build a useful quantum machine. But Raz and Tal’s paper demonstrates that quantum and classical computers really are a category apart — that even in a world where classical computers succeed beyond all realistic dreams, quantum computers would still stand beyond them.

A basic task of theoretical computer science is to sort problems into complexity classes. A complexity class contains all problems that can be solved within a given resource budget, where the resource is something like time or memory.

Computer scientists have found an efficient algorithm, for example, for testing whether a number is prime. They have not, however, been able to find an efficient algorithm for identifying the prime factors of large numbers. Therefore, computer scientists believe (but have not been able to prove) that those two problems belong to different complexity classes.

The two most famous complexity classes are “P” and “NP.” P is all the problems that a classical computer can solve quickly. (“Is this number prime?” belongs to P.) NP is all the problems that classical computers can’t necessarily solve quickly, but for which they can quickly verify an answer if presented with one. (“What are its prime factors?” belongs to NP.) Computer scientists believe that P and NP are distinct classes, but actually proving that distinctness is the hardest and most important open problem in the field.

In 1993 computer scientists Ethan Bernstein and Umesh Vaziranidefined a new complexity class that they called BQP, for “bounded-error quantum polynomial time.” They defined this class to contain all the decision problems — problems with a yes or no answer — that quantum computers can solve efficiently. Around the same time they also proved that quantum computers can solve all the problems that classical computers can solve. That is, BQP contains all the problems that are in P.

But they could not determine whether BQP contains problems not found in another important class of problems known as “PH,” which stands for “polynomial hierarchy.” PH is a generalization of NP. This means it contains all problems you get if you start with a problem in NP and make it more complex by layering qualifying statements like “there exists” and “for all.”1 Classical computers today can’t solve most of the problems in PH, but you can think of PH as the class of all problems classical computers could solve if P turned out to equal NP. In other words, to compare BQP and PH is to determine whether quantum computers have an advantage over classical computers that would survive even if classical computers could (unexpectedly) solve many more problems than they can today.

“PH is one of the most basic classical complexity classes there is,” said Scott Aaronson, a computer scientist at the University of Texas at Austin. “So we sort of want to know, where does quantum computing fit into the world of classical complexity theory?”

The best way to distinguish between two complexity classes is to find a problem that is provably in one and not the other. Yet due to a combination of fundamental and technical obstacles, finding such a problem has been a challenge.

If you want a problem that is in BQP but not in PH, you have to identify something that “by definition a classical computer could not even efficiently verify the answer, let alone find it,” said Aaronson. “That rules out a lot of the problems we think about in computer science.”

Here’s the problem. Imagine you have two random number generators, each producing a sequence of digits. The question for your computer is this: Are the two sequences completely independent from each other, or are they related in a hidden way (where one sequence is the “Fourier transform” of the other)? Aaronson introduced this “forrelation” problem in 2009 and proved that it belongs to BQP. That left the harder, second step — to prove that forrelation is not in PH.

Which is what Raz and Tal have done, in a particular sense. Their paper achieves what is called “oracle” (or “black box”) separation between BQP and PH. This is a common kind of result in computer science and one that researchers resort to when the thing they’d really like to prove is beyond their reach.

The actual best way to distinguish between complexity classes like BQP and PH is to measure the computational time required to solve a problem in each. But computer scientists “don’t have a very sophisticated understanding of, or ability to measure, actual computation time,” said Henry Yuen, a computer scientist at the University of Toronto.

So instead, computer scientists measure something else that they hope will provide insight into the computation times they can’t measure: They work out the number of times a computer needs to consult an “oracle” in order to come back with an answer. An oracle is like a hint-giver. You don’t know how it comes up with its hints, but you do know they’re reliable.

If your problem is to figure out whether two random number generators are secretly related, you can ask the oracle questions such as “What’s the sixth number from each generator?” Then you compare computational power based on the number of hints each type of computer needs to solve the problem. The computer that needs more hints is slower.

“In some sense we understand this model much better. It talks more about information than computation,” said Tal.

The new paper by Raz and Tal proves that a quantum computer needs far fewer hints than a classical computer to solve the forrelation problem. In fact, a quantum computer needs just one hint, while even with unlimited hints, there’s no algorithm in PH that can solve the problem. “This means there is a very efficient quantum algorithm that solves that problem,” said Raz. “But if you only consider classical algorithms, even if you go to very high classes of classical algorithms, they cannot.” This establishes that with an oracle, forrelation is a problem that is in BQP but not in PH.

Raz and Tal nearly achieved this result almost four years ago, but they couldn’t complete one step in their would-be proof. Then just a month ago, Tal heard a talk on a new paper on pseudorandom number generators and realized the techniques in that paper were just what he and Raz needed to finish their own. “This was the missing piece,” said Tal.

News of the separation between BQP and PH circulated quickly. “The quantum complexity world is a-rocking,” wrote Lance Fortnow, a computer scientist at Georgia Tech, the day after Raz and Tal posted their proof.

The work provides an ironclad assurance that quantum computers exist in a different computational realm than classical computers (at least relative to an oracle). Even in a world where P equals NP — one where the traveling salesman problem is as simple as finding a best-fit line on a spreadsheet — Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve.

“Even if P were equal to NP, even making that strong assumption,” said Fortnow, “that’s not going to be enough to capture quantum computing.”

Correction June 21, 2018: An earlier version of this article stated that the version of the traveling salesman problem that asks if a certain path is exactly the shortest distance is “likely” to be in PH. In fact, it has been proved to be in PH.

SOURCE: https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/

MIT researchers are employing novel machine-learning techniques to improve the quality of life for patients by reducing toxic chemotherapy and radiotherapy dosing for glioblastoma, the most aggressive form of brain cancer.

Glioblastoma is a malignant tumor that appears in the brain or spinal cord, and prognosis for adults is no more than five years. Patients must endure a combination of radiation therapy and multiple drugs taken every month.

Medical professionals generally administer maximum safe drug doses to shrink the tumor as much as possible. But these strong pharmaceuticals still cause debilitating side effects in patients.

In a paper being presented at the 2018 Machine Learning for Healthcare conference at Stanford University, MIT Media Lab researchers detail a model that could make dosing regimens less toxic but still effective.

Powered by a “self-learning” machine-learning technique, the model looks at treatment regimens currently in use, and iteratively adjusts the doses. Eventually, it finds an optimal treatment plan, with the lowest possible potency and frequency of doses that should still reduce tumor sizes to a degree comparable to that of traditional regimens.

In simulated trials of 50 patients, the machine-learning model designed treatment cycles that reduced the potency to a quarter or half of nearly all the doses while maintaining the same tumor-shrinking potential. Many times, it skipped doses altogether, scheduling administrations only twice a year instead of monthly.

“We kept the goal, where we have to help patients by reducing tumor sizes but, at the same time, we want to make sure the quality of life — the dosing toxicity — doesn’t lead to overwhelming sickness and harmful side effects,” Pratik Shah, a principal investigator at the Media Lab who supervised this research, said.

The paper’s first author is Gregory Yauney, Media Lab researcher.

The researchers’ model uses a technique called reinforced learning (RL), a method inspired by behavioral psychology, where a model learns to favor certain behavior that leads to a desired outcome.

The technique comprises artificially intelligent “agents” that complete “actions” in an unpredictable, complex environment to reach a desired “outcome.” Whenever it completes an action, the agent receives a “reward” or “penalty,” depending on whether the action works toward the outcome. Then, the agent adjusts its actions accordingly to achieve that outcome.

Rewards and penalties are basically positive and negative numbers, say +1 or -1. Their values vary by the action taken, calculated by probability of succeeding or failing at the outcome, among other factors. The agent is essentially trying to numerically optimize all actions, based on reward and penalty values, to get to a maximum outcome score for a given task.

The approach was used to train the computer program DeepMind that in 2016 made headlines for beating one of the world’s best human players in the game “Go.” It’s also used to train driverless cars in maneuvers, such as merging into traffic or parking, where the vehicle will practice over and over, adjusting its course, until it gets it right.

The researchers adapted an RL model for glioblastoma treatments that use a combination of the drugs temozolomide (TMZ) and procarbazine, lomustine, and vincristine (PVC), administered over weeks or months.

The model’s agent combs through traditionally administered regimens. These regimens are based on protocols that have been used clinically for decades and are based on animal testing and various clinical trials. Oncologists use these established protocols to predict how much doses to give patients based on weight.

As the model explores the regimen, at each planned dosing interval, say, once a month, it decides on one of several actions. It can, first, either initiate or withhold a dose. If it does administer, it then decides if the entire dose, or only a portion, is necessary. At each action, it pings another clinical model, often used to predict a tumor’s change in size in response to treatments, to see if the action shrinks the mean tumor diameter. If it does, the model receives a reward.

However, the researchers also had to make sure the model doesn’t just dish out a maximum number and potency of doses. Whenever the model chooses to administer all full doses, therefore, it gets penalized, so instead chooses fewer, smaller doses.

“If all we want to do is reduce the mean tumor diameter, and let it take whatever actions it wants, it will administer drugs irresponsibly,” Shah said. “Instead, we said, ‘We need to reduce the harmful actions it takes to get to that outcome.’”

This represents an “unorthodox RL model, described in the paper for the first time,” Shah said, that weighs potential negative consequences of actions (doses) against an outcome (tumor reduction). Traditional RL models work toward a single outcome, such as winning a game, and take any and all actions that maximize that outcome. On the other hand, the researchers’ model, at each action, has flexibility to find a dose that doesn’t necessarily solely maximize tumor reduction, but that strikes a perfect balance between maximum tumor reduction and low toxicity. This technique has various medical and clinical trial applications, where actions for treating patients must be regulated to prevent harmful side effects.

The researchers trained the model on 50 simulated patients, randomly selected from a large database of glioblastoma patients who had previously undergone traditional treatments.

For each patient, the model conducted about 20,000 trial-and-error test runs. Once training was complete, the model learned parameters for optimal regimens. When given new patients, the model used those parameters to formulate new regimens based on various constraints the researchers provided.

The researchers then tested the model on 50 new simulated patients and compared the results to those of a conventional regimen using both TMZ and PVC. When given no dosage penalty, the model designed nearly identical regimens to human experts. Given small and large dosing penalties, however, it substantially cut the doses’ frequency and potency, while reducing tumor sizes.

The researchers also designed the model to treat each patient individually, as well as in a single cohort, and achieved similar results (medical data for each patient was available to the researchers).

Traditionally, a same dosing regimen is applied to groups of patients, but differences in tumor size, medical histories, genetic profiles, and biomarkers can all change how a patient is treated. These variables are not considered during traditional clinical trial designs and other treatments, often leading to poor responses to therapy in large populations, Shah said.

“We said [to the model], ‘Do you have to administer the same dose for all the patients? And it said, ‘No. I can give a quarter dose to this person, half to this person, and maybe we skip a dose for this person.’ That was the most exciting part of this work, where we are able to generate precision medicine-based treatments by conducting one-person trials using unorthodox machine-learning architectures,” Shah said.

The model offers a major improvement over the conventional “eye-balling” method of administering doses, observing how patients respond, and adjusting accordingly, Nicholas J. Schork, a professor and director of human biology at the J. Craig Venter Institute, and an expert in clinical trial design, said.

“[Humans don’t] have the in-depth perception that a machine looking at tons of data has, so the human process is slow, tedious, and inexact,” he added. “Here, you’re just letting a computer look for patterns in the data, which would take forever for a human to sift through, and use those patterns to find optimal doses.”

Schork added that this work may particularly interest the U.S. Food and Drug Administration that is now seeking ways to leverage data and artificial intelligence to develop health technologies.

Regulations still need be established, he said, “but I don’t doubt, in a short amount of time, the FDA will figure out how to vet these [technologies] appropriately, so they can be used in everyday clinical programs.”

SOURCE: https://www.laboratoryequipment.com/news/2018/08/ai-model-learns-patient-data-make-cancer-treatment-less-toxic

This is the device compared to a US dollar coin. Photo: Zhenlong Huang

By stacking and connecting layers of stretchable circuits on top of one another, engineers have developed an approach to build soft, pliable "3-D stretchable electronics" that can pack a lot of functions while staying thin and small in size.

The work was published in the Aug. 13 issue of Nature Electronics.

As a proof of concept, a team led by the University of California San Diego has built a stretchable electronic patch that can be worn on the skin like a bandage and used to wirelessly monitor a variety of physical and electrical signals, from respiration, to body motion, to temperature, to eye movement, to heart and brain activity.

The device is as small and thick as a US dollar coin, and can also be used to wirelessly control a robotic arm.

"Our vision is to make 3-D stretchable electronics that are as multifunctional and high-performing as today's rigid electronics," Sheng Xu, senior author and professor in the Department of NanoEngineering and the Center for Wearable Sensors, at the UC San Diego Jacobs School of Engineering, said.

Xu was named among MIT Technology Review's 35 Innovators Under 35 list in 2018 for his work in this area.

To take stretchable electronics to the next level, Xu and his colleagues are building upwards rather than outwards.

"Rigid electronics can offer a lot of functionality on a small footprint—they can easily be manufactured with as many as 50 layers of circuits that are all intricately connected, with a lot of chips and components packed densely inside. Our goal is to achieve that with stretchable electronics," Xu said.

The new device developed in this study consists of four layers of interconnected stretchable, flexible circuit boards.

Each layer is built on a silicone elastomer substrate patterned with what's called an "island-bridge" design. Each "island" is a small, rigid electronic part (sensor, antenna, Bluetooth chip, amplifier, accelerometer, resistor, capacitor, inductor, etc.) that's attached to the elastomer. The islands are connected by stretchy "bridges" made of thin, spring-shaped copper wires, allowing the circuits to stretch, bend and twist without compromising electronic function.

The recent work overcomes a technological roadblock to building stretchable electronics in 3-D.

"The problem isn't stacking the layers. It's creating electrical connections between them so they can communicate with each other," Xu said.

These electrical connections, known as vertical interconnect accesses or VIAs, are essentially small conductive holes that go through different layers on a circuit. VIAs are traditionally made using lithography and etching. While these methods work fine on rigid electronic substrates, they don't work on stretchable elastomers.

So Xu and his colleagues turned to lasers.

First, they mixed silicone elastomer with a black organic dye so that it could absorb energy from a laser beam. Then they fashioned circuits onto each layer of elastomer, stacked them and hit certain spots with a laser beam to create the VIAs.

Afterward, the researchers filled in the VIAs with conductive materials to electrically connect the layers to one another. And a benefit of using lasers, Xu noted, is that they are widely used in industry, so the barrier to transfer this technology is low.

The team built a proof-of-concept 3-D stretchable electronic device that they've dubbed a "smart bandage."

A user can stick it on different parts of the body to wirelessly monitor different electrical signals. When worn on the chest or stomach, it records heart signals like an electrocardiogram (ECG). On the forehead, it records brain signals like a mini EEG sensor, and when placed on the side of the head, it records eyeball movements. When worn on the forearm, it records muscle activity and can also be used to remotely control a robotic arm. The smart bandage also monitors respiration, skin temperature and body motion.

"We didn't have a specific end use for all these functions combined together, but the point is that we can integrate all these different sensing capabilities on the same small bandage," Zhenlong Huang, co-first author and who conducted this work as a visiting Ph.D. student in Xu's research group, said.

The researchers did not sacrifice quality for quantity.

"This device is like a 'master of all trades.' We picked high quality, robust subcomponents—the best strain sensor we could find on the market, the most sensitive accelerometer, the most reliable ECG sensor, high quality Bluetooth, etc.—and developed a clever way to integrate all these into one stretchable device," Yang Li, co-first author and a nanoengineering graduate student at UC San Diego in Xu's research group, said.

So far, the smart bandage can last for more than six months without any drop in performance, stretchability or flexibility. It can communicate wirelessly with a smartphone or laptop up to 10 meters away. The device runs on a total of about 35.6 milliwatts that is equivalent to the power from 7 laser pointers.

The team will be working with industrial partners to optimize and refine this technology. They hope to test it in clinical settings in the future.

Cyber criminals shut down parts of the Web in October 2016 by attacking the computers that serve as the internet’s switchboard. Their weapon of choice? Poorly secured Web cameras and other internet-connected gadgets that have collectively come to be known as the Internet of Things (IoT). The attack created a minor panic among people trying to visit Sony PlayStation Network, Twitter, GitHub and Spotify’s Web sites, but it had little long-term effect on internet use or the hijacked devices. Less than two years later, however, security experts are sounding the alarm over a new and possibly more nefarious type of IoT attack that “cryptojacks” smart devices, surreptitiously stealing their computing power to help cyber criminals make digital money.

Cryptocurrencies—so called because they use cryptography to secure transactions and mint new virtual coins—are generated when computers loaded with “cryptomining” software perform complex mathematical calculations. The calculations themselves serve no practical purpose, but the faster the computers complete them the more electronic money they make. Cryptojacking (a mashup of the words “cryptocurrency” and “hijacking”) occurs anytime someone uses another person’s internet-connected device without permission to “mine” Ethereum, Monero or some other virtual cash. (Bitcoins are a lot more valuable, but this well-known cryptocurrency is more likely to be created using warehouses of servers rather than someone’s stolen processing power).

Cyber criminals steal that power by sneaking malicious software containing cryptomining code onto PCs, smartphones and other internet-connected devices that, once infected, divert some of their processors’ capacity into solving the aforementioned calculations. Another type of cryptojacking attack occurs when internet users are tricked into visiting Web sites containing code that grabs part of their device’s processing power for as long as they visit the site. To entice people to stay, those sites tend to offer free pornography or pirated content. Victims usually have no idea their device has been coopted—although they might wonder why their batteries drain so quickly.

“When mining for gold, the person who works hardest with their pickaxe makes the most money,” says Richard Enbody, an associate computer science and engineering professor at Michigan State University. “In cryptomining, the pickaxe is an algorithm. The more complex the calculations it performs, the more processing power and energy it uses and the more money it earns.”

The latest trend is for criminals to infect appliances and other internet-connected devices with unwanted cryptomining software, Sherri Davidoff, CEO of cyber security firm LMG Security, said during a recent IoT cryptojacking webinar. “Many of these devices are unmonitored and highly vulnerable to simple attacks that exploit weak passwords and unpatched vulnerabilities,” Davidoff said. Nearly every case LMG is currently investigating has turned up cryptomining software, in addition to whatever other malware criminals installed on their victims’ computers, she added.

To test IoT devices’ susceptibility to having their processors hijacked to make cryptocurrency, Davidoff and her colleagues hacked into a Web camera in their lab and installed cryptomining software. After a day of calculating the camera managed to produce about three-quarters of a penny’s worth of Monero. Not exactly the motherlode, but those almost-pennies add up over time—especially if an attacker takes over thousands of Web cameras and leaves the software in place for a while, Davidoff said. Security cameras are a prime target because they connect to mostly unsecured public networks and are fairly generic—the same malware can be used to infect many different brands. In some cases these devices do not allow users to change their default security passwords.

“For financially-motivated cybercriminals, cryptojacking a large number of inadequately protected IoT devices could be highly lucrative,” says Pranshu Bajpai, a PhD candidate in Michigan State University’s Department of Computer Science and Engineering. “It can be argued that gaining [an] initial foothold into IoT devices is relatively easier than a computer or a phone, which normally have better protections.” Given that many IoT devices lack updated antivirus software or an intrusion detection system, the malware is more likely to remain undetected longer.

In addition to degrading battery life, cryptojacking can strain or possibly burn out a device’s processor. In an extreme case LMG investigated, one of the client’s employees requested an extremely powerful computer—ostensibly for work—only to inform the client within a couple of months that the computer had caught fire. A few weeks later the client discovered that the employee had been using his new work computer for cryptomining. Most cryptominers and hackers avoid overtaxing their machines, or the machines they hijack, for fear of killing a (digital) cash cow. Still, even if cryptojacking does not destroy a device it will slow it down considerably.

Not all remote cryptomining is done on the sly or for malicious purposes. In February lifestyle magazine Salon employed the practice to help make up for the advertising revenue they lose when readers use ad-blocking software. Salon began asking online readers to help support the publication financially, either by shutting off ad blockers or allowing Salon to borrow users’ devices for Monero mining while they read. UNICEF Australia encourages people to donate their computers’ processing power to the charity for digital fundraising. Cryptojacking, however, is increasingly being recognized as a crime. A Japanese court earlier this month sentenced a man to a year in prison for illegally cryptomining $45 in Monero on victims’ computers.

People can protect their devices primarily by keeping their operating systems and software up to date, Bajpai says. They can also install programs called “extensions,” which block mining software, in their Web browsers. Consumers typically must rely on the companies that make internet routers, Web cameras and other connected devices to keep that technology secure and up to date. If those companies do not ship their products with secure software and update it frequently to fight malware, the IoT could be in for a bumpy ride—and it is expected to grow from about 23 billion devices this year to more than 75 billion by 2025.

SOURCE: https://www.scientificamerican.com/article/how-cryptojacking-can-corrupt-the-internet-of-things/

Hortonworks’ VP International on the big data challenges of smart cities

The Need for Speed

See also: London’s New Smart City Roadmap: A LODA Good News on Data?

Data Intersection Points

Legacy Solutions Leave Gaps

Smart Cities Need a Modern Data Architecture