Quantum algorithms for combinatorial search and optimization problems
(collaborators: D. Timucin and U.V. Toussaint)
"Number partitioning via quantum adiabatic computation"
V. N. Smelyanskiy, U.V. Toussaint, quant-ph/0202155
Combinatorial search and optimization problems are frequently encountered in practice, with distinct relevance to many scientific and engineering applications. Most of the problems in combinatorial optimization are NP-hard which means that no classical algorithm is known that solves the problem significantly faster then exhaustive search of the domain. These are computationally intensive problems whose solution requires prohibitively (i.e., exponentially) large computing resources, thus essentially rendering them intractable.
Recently a new class of continues-time quantum algorithms has been suggested for combinatorial optimization problems that is based on the properties of quantum adiabatic evolution. The crucial difference between the quantum adiabatic algorithm and classical heuristics such as simulated annealing is related to the possibility of quantum tunneling between the spin configurations that are close in the energy space but can be far away in the configuration space. Numerical simulations on classical computer of quantum adiabatic algorithms for a number of NP-complete problems show that vast majority of problem instances that are intractable by any of existing classical search algorithms can be solved effectively (in polynomial time) on quantum computer. These numerical results suggest that for certain NP-complete problems quantum adiabatic algorithm corresponds to trajectories of a system in a Hilbert space that "avoid" large potential barriers due to connectivity properties of spin configuration space. On the other hand our recent results show that for certain NP-complete problems such as, e.g., Set Partition, solution can only be achieved in a time exponential in the problem size.
Therefore one of the central questions of classical complexity theory: "where the hard problems are" should now be re-addressed for the new emerging family of quantum optimization algorithms.
Research in our group is focused in this new direction: we use the ideas from theories of quantum control and spin glasses to describe the boundary of "quantum intractability" for NP-complete problems and suggest quantum heuristics algorithms that work well in the cases where classical heuristics fail. We also work on the approaches to quantum optimization that combine the properties of classical simulated annealing (such as noise-induced activation escape from the local minima) with the possibility of quantum tunneling between the minima.
Solid -state implementation of quantum
computing devices
(collaborator: D. Srivastava).
The successful implementation of quantum algorithms will require a specialized physical platform that is (i) highly scalable and (ii) highly coherent. Here, scalability refers to the ability of the system to manipulate and interconnect the quantum states of a large number (i.e., hundreds to thousands) of elementary information units ("qubits"), while coherence refers to the ability of the system to sustain the unitary (computational) evolution of its quantum wavefunction despite (unavoidable) interactions with external degrees of freedom (i.e., noisy reservoirs).
It is generally believed that a quantum computing implementation with impurities embedded in a semiconductor holds one of the biggest promises for the future. We peruse the approach to solid-state quantum computing in which logic operations and quantum memory is implemented using electronic and nuclear states of the dopant atoms inside diamond nanocrystals. Different qubits are coupled to each other by means of dipole-dipole interactions of electric or magnetic origin. Role of the diamond nanocrystals is to significantly screen the interaction of dopant atoms with exitations in the bulk material. This leads to an increase in the coherence time of qubit operation due to the much lower density of vibrations in nanodiamond as compared to bulk phonons. The other advantage of "diamond-coated" qubits is a precise control over the qubit positions and feasibility of assembling of a quantum computer.
Controlling large fluctuations in systems far from
thermal equilibrium
(collaborators: M.I. Dykman and B. Golding)
Large fluctuations play a key role in a broad range of physical processes, from cosmology and nucleation at phase transitions to mode switching and mode hopping in lasers, mutations in DNA sequences, and others. They are also of crucial importance in for engineering as they are often responsible for failures of systems and devices. Therefore control of large fluctuations is a challenging and fundamental problem. Despite numerous efforts no generally accepted principles have been found that describe the probabilities of large fluctuations in systems away from thermal equilibrium such as lasers and biological systems. On the other hand it is an emerging understanding that large fluctuations can play a creative role: they can strongly enhance a signal in nonlinear system and improve signal processing through stochastic resonance. They can also give rise to unidirectional current in spatially periodic structures.
We study the phenomena of large deviations in nonlinear dynamical systems in the presence of noise and dissipation. In particular, we are interested in the phenomena of escape from metastable states in periodically driven systems and nucleation in systems far from thermal equilibrium, such as electro-chemical nucleation.
New direction of our work is related to a model identification and learning control of nonlinear dynamical systems using large fluctuations in the time-series data away from stable states. System dynamics can be best learn in the vicinities of the most probable (least improbable) paths that system follows in thecourse of large fluctuations.
 |
 |
 |
 |
Phone: 650-604-2261