In laboratory and numerical experiments, physical quantities are known with a finite precision and described by rational numbers. Based on this, we deduce that quantum control problems both for open and closed systems are in general not algorithmically solvable, i.e., there is no algorithm that can decide whether dynamics of an arbitrary quantum system can be manipulated by accessible external interactions (coherent or dissipative) such that a chosen target reaches a desired value. This conclusion holds even for the relaxed requirement of the target only approximately attaining the desired value. These findings do not preclude an algorithmic solvability for a particular class of quantum control problems. Moreover, any quantum control problem can be made algorithmically solvable if the set of accessible interactions (i.e., controls) is rich enough. To arrive at these results, we develop a technique based on establishing the equivalence between quantum control problems and Diophantine equations, which are polynomial equations with integer coefficients and integer unknowns. In addition to proving uncomputability, this technique allows to construct quantum control problems belonging to different complexity classes. In particular, an example of the control problem involving a two-mode coherent field is shown to be NP-hard, contradicting a widely held believe that two-body problems are easy.
In laboratory and numerical experiments, physical quantities are known with a finite precision and described by rational numbers. Based on this, we deduce that quantum control problems both for open and closed systems are in general not algorithmically solvable, i.e., there is no algorithm that can decide whether dynamics of an arbitrary quantum system can be manipulated by accessible external interactions (coherent or dissipative) such that a chosen target reaches a desired value. This conclusion holds even for the relaxed requirement of the target only approximately attaining the desired value. These findings do not preclude an algorithmic solvability for a particular class of quantum control problems. Moreover, any quantum control problem can be made algorithmically solvable if the set of accessible interactions (i.e., controls) is rich enough. To arrive at these results, we develop a technique based on establishing the equivalence between quantum control problems and Diophantine equations, which are polynomial equations with integer coefficients and integer unknowns. In addition to proving uncomputability, this technique allows to construct quantum control problems belonging to different complexity classes. In particular, an example of the control problem involving a two-mode coherent field is shown to be NP-hard, contradicting a widely held believe that two-body problems are easy.
Realizing coherent quantum computation requires precise and robust manipulation of quantum systems through quantum control protocols. Most quantum control techniques rely on heuristic methods for designing the driving pulses that steer the system towards a target state. Such methods are often based on brute-force optimization and offer limited understanding of the solution landscape. In contrast, quantum algorithms offer a rich body of analytical methods with rigorous error guarantees for implementing unitary and non-unitary transformations, which suggests a promising direction for developing new approaches to quantum control. Among various such algorithms, quantum signal processing (QSP) has emerged as a powerful framework for quantum algorithm design, implementation, and optimization. However, its potential for quantum control remains largely unexplored. In this work, we establish QSP-Control, an analytical framework for quantum control of qubit-oscillator dynamics. We focus on dispersively coupled qubit-oscillator systems and employ the QSP formalism to mitigate unwanted nonlinear effects arising from cross-Kerr interactions. In addition, we develop constructions for precise manipulation of Fock states by designing Fock-state-selective operators, based on structural parallels between the Jaynes-Cummings interaction and QSP. These findings demonstrate how several practically relevant problems in quantum control can be mapped to forms amenable to QSP, offering both a systematic design framework and an interpretable perspective on quantum control.
All physical quantum systems are in contact with the external world which is inevitably a source of noise. It is therefore necessary to take into account this dissipation when designing controls that accomplish useful tasks in quantum information processing. This thesis is on that overlap of open quantum systems and control theory; it looks at what dynamics can happen with the use of external driving, and how this driving can be chosen to accomplish a desired goal. The first result looks at how a given quantum dissipator can be manipulated, using coherent controls, into replicating the action of a different type of noise. This results in no-go theorems for how noise can be transformed based on its isotropy, with applications in simulating open systems. Another way of doing simulations is to use only unitary dynamics over the system and a finite dimensional ancilla, and it is proved that there always exists a dilation Hamiltonian that replicates the noisy dynamics continuously in time. This also highlights the fact that adding controls on noise can result in a different evolution than if the controls were done on the under- lying system-environment level. A conjecture is introduced and studied which states that both approaches are equivalent in the special case of the controls commuting with the Lindbladian. A way around this difficulty is to use a quantum system to compute in situ which controls are best for achieving a desired task on itself. This problem is studied in the context of reaching entangling gates on a quantum simulator in order to upgrade it into a quantum computer. The experimental cost of doing so is found to be polynomial in the number of qubits in simulations. The same underlying principle is also used to find error correcting codes tailored to the dissipation in a system.
Quantum computing involving physical systems with continuous degrees of freedom, such as the quantum states of light, has recently attracted significant interest. However, a well-defined quantum complexity theory for these bosonic computations over infinite-dimensional Hilbert spaces is missing. In this work, we lay foundations for such a research program. We introduce natural complexity classes and problems based on bosonic generalizations of BQP, the local Hamiltonian problem, and QMA. We uncover several relationships and subtle differences between standard Boolean classical and discrete variable quantum complexity classes and identify outstanding open problems. In particular: 1. We show that the power of quadratic (Gaussian) quantum dynamics is equivalent to the class BQL. More generally, we define classes of continuous-variable quantum polynomial time computations with a bounded probability of error based on higher-degree gates. Due to the infinite dimensional Hilbert space, it is not a priori clear whether a decidable upper bound can be obtained for these classes. We identify complete problems for these classes and demonstrate a BQP lower and EXPSPACE upper bound. We further show that the problem of computing expectation values of polynomial bosonic observables is in PSPACE. 2. We prove that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard. Furthermore, we show that the problem of finding the minimum energy of a bosonic Hamiltonian critically depends on the non-Gaussian stellar rank of the family of energy-constrained states one optimizes over: for constant stellar rank, it is NP-complete; for polynomially-bounded rank, it is in QMA; for unbounded rank, it is undecidable.
Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA), are widely studied as candidates for near-term quantum advantage. Recent work has shown that training VQAs is NP-hard in general. In this paper, we present a conditional result suggesting that the training of VQAs is undecidable, even in idealized, noiseless settings. We reduce the decision version of the digitized VQA training problem-where circuit parameters are drawn from a discrete set-to the question of whether a universal Diophantine equation (UDE) has a root. This reduction relies on encoding the UDE into the structure of a variational quantum circuit via the matrix exponentials. The central step involves establishing a correspondence between the objective function of the VQA and a known UDE of 58 variables and degree 4. Our main result is conditional on a natural conjecture: that a certain system of structured complex polynomial equations-arising from the inner product of a VQA circuit output and a fixed observable-has at least one solution. We argue this conjecture is plausible based on dimension-counting arguments (degrees of freedom in the Hamiltonians, state vector, and observable), and the generic solvability of such systems in algebraic geometry over the complex numbers. Under this assumption, we suggest that deciding whether a digitized VQA achieves a given energy threshold is undecidable. This links the limitations of variational quantum algorithms to foundational questions in mathematics and logic, extending the known landscape of quantum computational hardness to include uncomputability. Additionally, we establish an unconditional undecidability result for VQA convergence in open quantum systems.
A closed quantum system is defined as completely controllable if an arbitrary unitary transformation can be executed using the available controls.In practice, control fields are a source of unavoidable noise, which has to be suppressed to retain controllability.Can one design control fields such that the effect of noise is negligible on the time-scale of the transformation?This question is intimately related to the fundamental problem of a connection between the computational complexity of the control problem and the sensitivity of the controlled system to noise.The present study considers a paradigm of control, where the Lie-algebraic structure of the control Hamiltonian is fixed, while the size of the system increases with the dimension of the Hilbert space representation of the algebra.We find two types of control tasks, easy and hard.Easy tasks are characterized by a small variance of the evolving state with respect to the operators of the control operators.They are relatively immune to noise and the control field is easy to find.Hard tasks have a large variance, are sensitive to noise and the control field is hard to find.The influence of noise increases with the size of the system, which 4
The interface between the quantum and the classical is an intriguing and, at times, hotly contested subject of ongoing research. The quantum regime is characterized by interference, made possible by the superposition principle, while such phenomena are absent in macroscopic, everyday experience. Here, we investigate the link of this absence (or, as we will argue, unobservability) to computational complexity. We show how the assumption that quantum systems cannot solve NP-complete problems efficiently implies that certain formally valid quantum measurements on finite-dimensional systems are unperformable. We study several consequences of this restriction. First, Pauli matrices in an inconveniently transformed basis are a simple example of unobservables. Furthermore, some quantum states are not connected by any physically realizable time evolution. Finally there are quantum states whose coherence cannot be observed, i.e. superpositions of pure quantum states which are indistinguishable from mixtures. We discuss the connection of this phenomenon to the presence of superselection sectors. Our results suggest that the apparent classicality of macroscopic systems may be partly due to limitations on measurements and time evolutions imposed by computational complexity.