Quantum Computing Tackles Complex Control Theory Problems: Verifying Interval Matrix Properties

Quantum computing, known for its ability to solve complex computational problems, is being explored for its potential in verifying interval matrix properties, a task known to be computationally challenging. Variational quantum algorithms (VQAs), particularly the quantum approximate optimization algorithm (QAOA), are being used to tackle this problem. Researchers from the University of Stuttgart have proposed a quantum algorithm based on QAOA to verify robust nonsingularity and robust stability of interval matrices. This research, funded by the German Research Foundation, marks a significant step in applying quantum computing to systems and control theory.

What is the Role of Quantum Computing in Control Interval Matrix Properties?

Quantum computing, a powerful framework for tackling computational problems that are classically intractable, has been gaining increasing attention in recent years. This is due to its ability to solve certain computationally challenging problems more efficiently than classically possible. This includes integer factorization, unstructured search, linear systems of equations, and the simulation of classical and quantum systems. However, these algorithms cannot be implemented reliably for relevant problem sizes on current noisy intermediate-scale quantum (NISQ) devices due to problems connected to noise and scalability.

Variational quantum algorithms (VQAs) are a promising class of quantum algorithms which combine a quantum computer with a classical optimization algorithm. VQAs involve trainable parameters which are optimized iteratively using a gradient descent scheme and therefore they are well-suited for NISQ devices due to their adaptation to small and noisy hardware. The quantum approximate optimization algorithm (QAOA) is one of the most popular VQAs and it can be used to solve a specific class of integer programs, quadratic unconstrained binary optimization (QUBO) problems.

Problems with integer variables are relevant in various domains of systems and control theory and therefore QAOA is a promising candidate for achieving computational speedups in control. Yet the usage of quantum computers in control is largely unexplored. In this paper, an algorithm for the verification of interval matrix properties, which is known to be a computationally hard problem, is proposed for implementation on a quantum computer.

How are Quantum Computers Used in Verifying Interval Matrix Properties?

In computational complexity theory, problems can be classified according to the time required for their solution. Problems which can be solved with a polynomial-time algorithm belong to class P and those whose solution can be verified in polynomial time belong to class NP. For NP-hard problems, which are problems to which every problem in NP can be reduced efficiently, there exist no known polynomial-time algorithms on a classical computer. Various control-theoretic problems have been shown to be NP-hard, including static output feedback design or verifying interval matrix properties.

This paper introduces an approach for verifying interval matrix properties on a quantum computer. The focus is on two main properties: robust nonsingularity and robust stability of interval matrices, meaning that all members of the interval matrix are nonsingular or stable respectively. Existing research shows that the verification of robust nonsingularity can be equivalently reformulated as a binary optimization problem. Given that this binary optimization problem is a QUBO problem, it can be tackled using QAOA. The main contribution of this paper is a quantum algorithm based on QAOA which can verify robust nonsingularity and robust stability of interval matrices. The applicability is illustrated with numerical examples.

What is the Concept of Interval Matrices?

An interval matrix is defined as a matrix where each element is an interval, i.e., a set of real numbers lying between a lower and an upper bound. The center of an interval matrix is defined as the average of the lower and upper bound matrices. This allows to reformulate the lower and upper bound matrices in terms of the center and a distance matrix.

In this paper, the study of nonsingularity of interval matrices is based on the radius of nonsingularity. The definition of a nonsingular interval matrix is given as an interval matrix that is nonsingular if all matrices within the interval are nonsingular. The radius of nonsingularity measures the distance of a matrix to the closest singular matrix according to an a priori fixed shifting matrix.

How is Quantum Computing Applied to Interval Matrices?

The verification of robust nonsingularity can be equivalently reformulated as a binary optimization problem. Given that this binary optimization problem is a QUBO problem, it can be tackled using QAOA. The main contribution of this paper is a quantum algorithm based on QAOA which can verify robust nonsingularity and robust stability of interval matrices. The applicability is illustrated with numerical examples.

The authors of the paper, Jan Schneider and Julian Berberich, are with the Institute for Systems Theory and Automatic Control, University of Stuttgart, Germany. The research was funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy and supported by the Stuttgart Center for Simulation Science (SimTech).

What are the Implications of this Research?

The research presented in this paper demonstrates that quantum computers provide a promising tool for control, particularly in the verification of interval matrix properties. This is a significant step forward in the application of quantum computing to systems and control theory, a field that has been largely unexplored. The quantum algorithm developed in this study has the potential to tackle computationally complex problems more efficiently than classical methods, opening up new possibilities for advancements in this field. However, the applicability of quantum computers to further computationally complex problems remains to be explored.