Analytical optimization and
complexity theory
My interest in the theory of computational complexity stems from the fact that numerical optimization is required to solve many problems in my areas of interest, and complexity theory is a useful tool for comparing the power of optimization algorithms.
For example, since most problems in optimal control theory do not admit analytical solutions, it is necessary to search numerically (or experimentally, through closed loop methods) for the best controls. Because these optimizations are carried out on (formally) infinite-dimensional spaces, they can be computationally very expensive. Assessment of algorithmic complexity is particularly useful for such optimizations over function spaces.
The study of the algorithmic complexity of noncombinatorial optimization problems is a relatively new field, and surprisingly few analytical solutions currently exist. In fact, in theoretical computer science, the appropriate complexity theory appropriate for such analog computations is still hotly debated. Conveniently, in quantum esimation and control, it is in certain cases possible to derive analytical results pertaining to the scaling of convergence time of numerical algorithms. In the cases where this is not possible, characterization of the topology of the search space may still be useful.
Computational complexity of quantum optimal control landscapes
R. Chakrabarti, R. Wu, K. Steiglitz and H. Rabitz, in preparation (2008).
Eprint arXiv:0708.3513 [quant-ph] (2007)
We study the system-independent contribution to the complexity of quantum optimal control problems. Given the computational expense of propagating the Schrodinger equation, the scaling with system size of the expense of executing a search over the space of control fields -- referred to as the problem's computational complexity -- plays an essential role in determining the feasibility and efficiency of control optimizations in large quantum systems. The complexity of control optimization for quantum gates is of particular interest, as it corresponds to the classical complexity associated with the physical implementation of quantum logical operations.
Critical topology for optimization on the Symplectic group
R. Wu, and R. Chakrabarti and H. Rabitz, J. Geom. Phys., submitted (2008).
Eprint arXiv:0708.3822 [quant-ph]
This is a pure
mathematics paper on the topology of functions defined on
noncompact Lie
groups. An example is the symplectic Lie group, which can be used to
represent continuous
variable quantum gates.
The simple topology of these functions underlies the success of optimal
control strategies for the implementation of computing gates in
quantum optical systems.
The absence of local traps in control landscapes for symplectic gate fidelity indicates that given sufficient time, local gradient-based algorithms will generally succeed at reaching the global optima (perfect fidelity), assuming the system is controllable. This property, combined with other attractive features of continuous quantum information processing (QIP) such as the high bandwidth of continuous degrees of freedom, strengthens the feasibility of QIP over continuous variables.
The absence of local traps in control landscapes for symplectic gate fidelity indicates that given sufficient time, local gradient-based algorithms will generally succeed at reaching the global optima (perfect fidelity), assuming the system is controllable. This property, combined with other attractive features of continuous quantum information processing (QIP) such as the high bandwidth of continuous degrees of freedom, strengthens the feasibility of QIP over continuous variables.
Next steps
Although we have identified the system-independent contribution to the complexity of quantum control optimization problems, this information only allows us to compare the relative difficulty of different classes of quantum control problems. Our next step is to assess the absolute scaling of problem difficulty with system size.