Dario Pighin\(^*\)

Irontec, Internet y sistemas sobre GNU/Linux, S.L.

c/Uribitarte, 6-2º (Bilbao – 48001), Spain

E-mail: dpighin@irontec.com

We develop a control-theoretic framework for understanding Quantum Advantage (QA), providing a systematic route to characterize when and how QA can arise. The bilinear controlled Schrödinger equation is the common thread: the target quantum computation is recast as an operator controllability problem on the special unitary group \(SU(N)\), and QA is identified with a polynomial-in-\(n\) upper bound on the associated minimal-time function.

We illustrate the framework on two paradigmatic problems:

1. the Quantum Fourier Transform (QFT) on superconducting digital quantum processors (such as IBM’s ibm_brisbane), for which we prove operator controllability by a Lie-algebraic argument and derive an \(O(n^2)\) upper bound on the minimal time via a gate-concatenation lemma combined with the standard QFT circuit decomposition;

2. the Maximum Independent Set (MIS) problem on neutral-atom analog quantum processors (such as Pasqal’s hardware), for which we analyze the Rydberg-blockade Hamiltonian as a bilinear control system and reformulate Quantum Approximate Optimization Algorithm (QAOA) as a continuous-time optimal control problem. By a controllability result, we show how the problem can be solved on Pasqal Quantum Computers and we introduce a control-based definition of Quantum Advantage for MIS.

We conclude by outlining several open problems that chart directions for future research at the intersection of Control Theory and Quantum Computing.

1 Introduction↩︎

The purpose of these notes is to address the following question:

• For a given problem, is there a Quantum Advantage (QA) in solving it on a quantum computer ?

Under appropriate assumptions, the answer is positive. A paradigmatic example is the Quantum Fourier Transform (QFT) (see, e.g. [1]), the main building block of several celebrated quantum algorithms, such as Shor’s algorithm for prime factorization [2] or the HHL algorithm [3] to solve linear systems of equations. A second, structurally different example is the Maximum Independent Set (MIS) problem (see figure 1), which is NP-hard in the classical sense [4] and admits a natural analog quantum encoding on neutral-atom hardware via the Rydberg blockade mechanism [5]–[7]. Our goal is to answer the above question by control-theoretic tools, with the hope of building a systematic approach to assess whether Quantum Advantage (QA) holds, for a wide class of algorithms and hardware platforms.

Concretely, we illustrate the framework on two representative use cases:

1. QFT on superconducting (digital, gate-based) quantum computers, such as IBM’s ibm_brisbane;

2. MIS on neutral-atom (analog) quantum computers, such as Pasqal’s FRESNEL device, endowed Orion Quantum Processing Unit (QPU)¹.

These two cases cover the two complementary paradigms of universal digital quantum computation and analog quantum optimization, and exercise, respectively, operator controllability (QFT) and bilinear optimal control (MIS-QAOA) within one unified framework.

Quantum computing exploits the principles of quantum mechanics (superposition and entanglement) to perform computations in ways that can vastly outperform classical algorithms for certain tasks [1]. This gap in computational power is often referred to as Quantum Advantage (QA) , the ability of a quantum device to solve a problem beyond the feasible reach of classical computers in any reasonable time. A famous example is Shor’s algorithm for integer factorization, which runs in polynomial time on a quantum computer whereas the best known classical methods require super-polynomial time [1], [2], [8], [9]. The Shor’s algorithm is in fact based on Quantum Fourier Transform (QFT).

The quantum computer was conceived by Richard P. Feynman in the celebrated paper [10] for physical simulation. More recently, Quantum Computers are designed to run general computations (see, e.g. [1], [11] and references therein). Moreover, extending Richard P. Feynman’s idea, in recent works like [12], specific change of variables named Schrödingerization are proposed to allow running general Partial Differential Equation (PDE) simulation in a quantum computers.

In recent years, experimental demonstrations of Quantum Advantage (QA) have been a major milestone in the field. On the digital side, superconducting quantum processors, such as those developed by IBM and Google, have executed specialized sampling problems believed to be classically intractable. In particular, IBM’s cloud quantum computing platform now provides access to superconducting devices (e.g., the 127-qubit ibm\(\_\)brisbane or the 156-qubit ibm_BasqueCountry installed in Donostia - Basque Country) that enable researchers to explore quantum algorithms on real hardware². On the analog side, neutral-atom quantum processors, such as those developed by Pasqal [5] and QuEra [7], have demonstrated the ability to solve combinatorial optimization problems (in particular, Maximum Independent Set on unit-disk graphs) with hundreds of atoms, exploiting the Rydberg blockade mechanism for native constraint enforcement. These developments underscore the practical quest for Quantum Advantage (QA) across both paradigms and motivate a deeper theoretical understanding of how and when it can be achieved.

Achieving Quantum Advantage (QA) in practice hinges on the ability to control quantum systems with high precision. On a superconducting quantum computer, each logical qubit operation is implemented by externally applied control fields (e.g., shaped microwave pulses) that drive the evolution of the qubits’ quantum state. On a neutral-atom analog processor, the many-body atomic register is globally steered by laser fields with programmable Rabi frequency and detuning, together with a programmable spatial arrangement of the atoms. In both cases, the computation is an externally controlled trajectory in Hilbert space, and this places quantum computing squarely in the domain of Control Theory. In classical Control Theory, a dynamical system governed by differential equations is called controllable if one can drive the system from any given initial state to any desired final state by choosing appropriate control inputs [13], [14]. The concept of controllability is fundamental: it formalizes the intuitive notion of having complete command over a system’s behavior. Classical results, such as Kalman’s rank condition for linear systems, provide clear criteria for controllability in finite dimensions [13]. For more complex systems described by Partial Differential Equations (PDEs), powerful tools have been developed to analyze controllability and observability [14].

The integration of Control Theory with quantum mechanics has given rise to a rich interdisciplinary field of Quantum Control that is providing novel insights into both physics and engineering [15]–[19]. In the quantum domain, controllability typically means the ability to implement an arbitrary unitary transformation or prepare any target state in the Hilbert space of the system, given a suitable set of control Hamiltonians [17]. For many finite-dimensional quantum systems (such as a register of superconducting qubits), one can establish controllability via the Lie-algebraic rank condition: the Lie algebra generated by the system’s drift and control Hamiltonians spans the entire \(\mathfrak{su}(N)\) algebra (for an \(N\)-dimensional Hilbert space), ensuring that any unitary operation is reachable [17]. In practical terms, this implies a quantum computer with controllable qubits is, in principle, a universal computing device. Of course, practical limitations like decoherence and imperfect actuators mean not every unitary is achievable with high fidelity, but the theoretical notion of controllability provides an important benchmark. Infinite-dimensional quantum systems has been analyzed as well by Control Theory. For those systems, the Schrödinger equation is a Partial Differential Equation (PDE). Some references on the application of PDE Control Theory to the Schrödinger equation are [14], [20]–[24] and references therein. In essence, quantum hardware presents a rich, high-dimensional control system, and the challenge is to steer it through its exponentially large state space efficiently and accurately.

In addition to controllability, Optimal Control plays a vital role in quantum computing. Optimal Control Theory asks: given a controllable system, what is the best way to steer it to achieve a desired objective while minimizing a cost (such as time, energy, or error)? [17] Quantum Optimal Control techniques have been widely applied to design pulse sequences that implement quantum logic gates or state transfers with high fidelity and minimal duration. For instance, gradient-based algorithms can optimize microwave control pulses to carry out a quantum gate on superconducting qubits in the shortest possible time, respecting hardware constraints. The use of Optimal Control has become a cornerstone in improving quantum operations, reducing error rates, and pushing quantum devices closer to the regimes required for demonstrating Quantum Advantage (QA).

Given this backdrop, in this work we investigate the existence of Quantum Advantage (QA) from a control-theoretic perspective. We ask whether the superior computational power of quantum systems can be formally understood (and even quantified) through the lens of controllability and Optimal Control. By viewing a quantum algorithm as a controlled dynamical trajectory in Hilbert space, we can analyze what aspects of that trajectory might be intractable for any classical controller or classical computer to replicate. Our approach is theoretical: we derive analytical results that connect control-theoretic properties of quantum systems to their computational capabilities. In particular, we propose criteria based on control complexity and reachable sets that, if satisfied by a quantum system, would imply a provable Quantum Advantage (QA) for a certain class of problems. This amounts to a theoretical proof-of-concept for Quantum Advantage (QA), grounded in Control Theory, which does not rely on specific hardware experiments. For the moment, our results remain in the realm of mathematical analysis; however, they lay the groundwork for future experimental validation on physical quantum processors. Moreover, our approach paves the way of a control-inspired improvement of quantum algorithms.

This paper is written for an interdisciplinary audience of control theorists and quantum physicists. We therefore review the necessary background from both fields and strive to use terminology accessible to each community. We highlight how Control Theory concepts such as controllability and Optimal Control can provide fresh insights into quantum computation, and conversely, how quantum computing motivates new questions in Control Theory. Our hope is that this synergy between control and quantum dynamics will not only help in rigorously establishing Quantum Advantage (QA), but also foster collaboration between the two disciplines in addressing the challenges of quantum technology.

In chapter 2, we introduce the mathematical framework for Quantum Computing (QC), inspired from [1]: the state space, the bilinear controlled Schrödinger equation, the notion of operator controllability and the control-theoretic definition of Quantum Advantage. Chapter 3 is devoted to the first representative problem: we model superconducting quantum computers (such as ibm\(\_\)brisbane) by a controlled Schrödinger equation, prove operator controllability by standard Lie-algebraic methods, and establish Quantum Advantage for the QFT by combining a gate-concatenation lemma with the well-known \(O(n^2)\) circuit decomposition. Chapter 4 is devoted to the second representative problem: we introduce the MIS problem, model neutral-atom quantum computers (such as Pasqal’s hardware) by a Rydberg-blockade Hamiltonian, reformulate QAOA as a bilinear optimal control problem, show that MIS is solvable on Pasqal devices, and discuss the scope of Quantum Advantage in this analog setting. Chapter 8 formulates a surrogate optimal control problem on the commutator \([U(t)\Gamma^*, H_0]\) providing a checkable necessary condition for Quantum Advantage applicable to both paradigms. We conclude the manuscript by collecting some open problems in chapter 5. The appendix includes quantum speed limits on \(SU(N)\) via bi-invariant Riemannian geometry, a discussion of the steady-control case, and an explicit example of drift Hamiltonian.

2 Mathematical framework↩︎

The quantum computer works by controlling quantum processes running on specific (quantum) physical systems.

Typically, in quantum computing, the state space is modeled as a Hilbert space over \(\mathbb{C}\) of the form \[\label{state95space} \mathcal{H} \overset{\scriptscriptstyle\mathrm{def}}{=}\underbrace{\mathbb{C}^2 \otimes \dots \otimes \mathbb{C}^2}_{n\text{ times}} = \bigotimes_{j=1}^n \mathbb{C}^2,\tag{1}\] which has dimension³ \(N = 2^n\) for some \(n \in \mathbb{N}\).

In the language of projective geometry, a quantum state is an element of the projective space \(\mathbb{P}(\mathcal{H})\) defined from \(\mathcal{H}\).

To simplify the terminology, a representative of a quantum state is often referred to as quantum state.

Given a state space as 1 , we postulate the time-evolution of the quantum system is described by the Schrödinger equation \[\label{ger32equation} i\frac{d}{dt}\mathbf{\psi}(t) = \big(H_0 + \sum_{j=1}^{m}u_j(t)H_j\big)\mathbf{\psi}(t),t\in(0,T),\tag{2}\] where

• the state of the control system is a function of time \(\mathbf{\psi}:[0,T]\longrightarrow \mathcal{H}\) evolving in the state space \(\mathcal{H}\);

• the drift hamiltonian \(H_0\) describes the free dynamics;

• the scalar controls \(u_j:[0,T] \longrightarrow \mathbb{R}\) are \(L^{\infty}(0,T)\) functions acting in the system by multiplication by the respective control hamiltonians \(H_j\);

• both the drift hamiltonian \(H_0\) and the control hamiltonians \(H_j\) are self-adjoint;

• the time horizon \(T>0\) is the decoherence time for the quantum system (see DiVincenzo criterion D5 [31], the notes [32] and [1]).

The equivalence of the above postulate and the time discrete one (where quantum evolution is described by unitary transformations) can be found in [1].

Studying the control properties of the above equation is the object of quantum Control Theory (see, e.g., [16], [19], [22], [33], [34] and references therein), applied directly to QFT problem in [35].

2.1 Quantum computation as a controllability problem↩︎

In a quantum algorithm, we have three steps

1. Initialize, where the quantum system is initialized to a quantum state \(\mathbf{\psi}_0\in \mathcal{H}\);

2. Compute, where the quantum system evolves, from the initial state \(\mathbf{\psi}_0\in \mathcal{H}\) to a final state \(\mathbf{\psi}_1\in \mathcal{H}\), employing in 2 specific controls;

3. Measure, where measurement is performed to check the result.

In this manuscript, we focus on the study of the computation (the second step). In what follows we define a quantum computation problem in terms of the operator controllability of the Schrödinger equation 3 . Arbitrarily fix \(M>0\) and define \[L^{\infty}_{M}(0,T)\overset{\scriptscriptstyle\mathrm{def}}{=}\left\{u_j:[0,T]\longrightarrow \mathbb{R} \;| \;|u(t)|\leq M, \;a.e. \;t\in [0,T]\right\}.\] Our control space is \[\label{control95functions95space} \mathscr{U}^T\overset{\scriptscriptstyle\mathrm{def}}{=}\left\{(u_j)_{j=1}^m \;| \;u_j\in L^{\infty}_{M}(0,T) \;for all j\in\left\{1,\dots,m\right\}\right\}=L^{\infty}(0,T)^m.\tag{5}\]

Let us formulate a quantum computation problem as an operator controllability problem (see, e.g., [19] and [17]).

The above operator controllability is verified in case the Lie algebra generated by \[\left\{-iH_0,-iH_1,\dots,-iH_j,\dots,-iH_m\right\}\] equals the Lie algebra \(su(N)=su(2^n)\) ([17]).

Let us now define the concept of Quantum Advantage (QA) by Optimal Control.

Assume 2 is operator controllable. For some target unitary operator \(\Gamma:\mathcal{H}\longrightarrow \mathcal{H}\), define the minimal controllability time⁵ \[\label{def95min95time} T_{\tiny{min}} \overset{\scriptscriptstyle\mathrm{def}}{=}\inf\left\{T>0 \;\big| \;\exists u\in \mathscr{U}_{\tiny{ad}}, \; U(T)=\Gamma\right\},\tag{8}\] where \(U:[0,+\infty)\longrightarrow \mathcal{M}_{N\times N}(\mathbb{C})\) represents the state, solution to the Cauchy problem \[\label{matrix95schrodinger95inftime} \begin{cases} i\frac{d}{dt}U(t) = \big(H_0 + \sum_{j=1}^{m}u_j(t)H_j\big)U(t),& t\in (0,+\infty)\\ U(0)=I,\\ \end{cases}\tag{9}\] with control \(u=(u_j)_{j=1}^m\) .

The above definition is well-posed. Indeed, for every target operator \(\Gamma:\mathcal{H}\longrightarrow \mathcal{H}\), by operator controllability, there exists a time horizon \(\overline{T}>0\) and a control \(u\in \mathscr{U}_{\tiny{ad}}\), such that \(U(\overline{T})=\Gamma\), whence \[\inf\left\{T>0 \;\big| \;\exists u\in \mathscr{U}_{\tiny{ad}}, \; U(T)=\Gamma\right\}\leq \overline{T}<+\infty;\]

Moreover, the infimum in 8 is achieved, as we illustrate in the following remark.

We conjecture the control in the minimal time is of bang-bang form. We imposed the constraint \(|u(t)|\leq M\) in view of our concrete use case. Checking whether the infimum is still achieved, removing the constraint, is an interesting research line.

A large literature is available on time optimal Quantum Control. See, e.g., [16], [38], [17] and references therein.

3 Quantum Advantage for the Quantum Fourier Transform↩︎

The purpose of this chapter is to show how Quantum Advantage is achieved by superconducting computers. As we mentioned, this is a well-known result (see, e.g. [1]).

3.1 Superconducting quantum computers↩︎

This section introduces a controlled Schrödinger equation for superconducting quantum computers. The definition of Pauli matrices acting on one qubit can be found in the last subsection. For the sake of concreteness, we focus on ibm_brisbane Quantum Computer. Our analysis applies to other quantum computers, like
ibm_BasqueCountry.

3.1.1 Quantum State Space↩︎

The quantum state space of the ibm_brisbane quantum computer is \[\label{ibmbrisbanestatespace} \mathcal{H} = \underbrace{\mathbb{C}^2 \otimes \dots \otimes \mathbb{C}^2}_{127\text{ times}} = \mathbb{C}^{2^{127}}\tag{11}\] corresponding to 127 qubits (whence \(\dim(\mathcal{H})=2^{127}> 10^{38}\)).

3.1.2 Coupling map↩︎

The coupling map \(\mathcal{E}\) is a directed graph defining connection among physical qubits in the computer (see figure 2).

• The graph nodes are the physical qubits.

• As we shall see, the graph edges represent permitted control operations across different qubits.

See [39]–[41] and the IBM documentation on Coupling Map. It is possible to get \(\mathcal{E}\), by running in Qiskit the command IBMBackend('ibm_brisbane').coupling_map (as in IBMBackend).

3.1.3 Controlled Schrödinger Equation↩︎

The evolution of the system is governed by the bilinear Schrödinger equation: \[\label{ibm95equation95control} i\frac{d}{dt}\mathbf{\psi}(t) = \big(H_0 + \sum_{j=1}^{m}u_j(t)H_j\big)\mathbf{\psi}(t),t\in(0,T),\tag{12}\] where

• \(H_0\) is the drift Hamiltonian (time-independent),

• \(H_j\) are the control Hamiltonians associated with time-dependent scalar controls \(u_j(t)\).

3.1.3.1 Drift Hamiltonian \(H_0\)

The drift Hamiltonian is a \(N\times N\) self-adjoint matrix with zero trace.

An example of drift Hamiltonian is in section 7 of the Appendix.

3.1.3.2 Control Hamiltonians \(H_j\)

The control Hamiltonians represent the microwave drives and cross-resonance interactions:

• Single-qubit drives: \[H_{\text{drive},k}(t) = u_k^X(t) X_k + u_k^Y(t) Y_k\] for each qubit \(k = 1, \dots, 127\) (see [39] and [17]).

• Cross-resonance drives: \[H_{\text{CR},c\to t}(t) = v_{ct}(t) Z_c \otimes X_t\] for each control-target qubit pair \((c,t) \in \mathcal{E}\) (see [42], [43]), \(\mathcal{E}\) representing the coupling map, presented in subsection 3.1.2.

The ibm_brisbane processor utilizes a heavy-hex lattice topology, optimizing the layout for cross-resonance gates. Below is a schematic representation of its qubit connectivity.

The Schrödinger equation 12 can be rewritten as \[\label{ibm95brisbane95equation} i \frac{d}{dt} {\psi(t)} = \Bigg( H_0 + \sum_{k=1}^{127} \left( u_k^X(t) X_k + u_k^Y(t) Y_k \right) + \sum_{(c,t) \in \mathcal{E}} v_{ct}(t) Z_c \otimes X_t \Bigg) {\psi(t)}.\tag{13}\]

Further references for superconducting quantum computers are [32], [44]–[46].

3.1.4 Pauli matrices↩︎

We use the standard Pauli matrices: \[I = \sigma_0 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad X = \sigma_x = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad Y = \sigma_y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad Z = \sigma_z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix},\] in the notation of [1].

Note that \[\label{square95pauli95matrices} X^2=I,Y^2=I,Z^2=I.\tag{14}\]

When we write \(X_k\), \(Y_k\), or \(Z_k\), we mean

• the Pauli matrix (\(X\), \(Y\), or \(Z\)) acts on qubit \(k\),

• the identity matrix \(I\) acts on all other qubits.

Formally, for a 127-qubit system: \[X_k = I^{\otimes k-1} \otimes X \otimes I^{\otimes (127 - k)}=\underbrace{I \otimes \dots \otimes I}_{k-1\text{ times}}\otimes X \otimes \underbrace{I \otimes \dots \otimes I}_{127 - k\text{ times}},\] and similarly for \(Y_k\) and \(Z_k\).

For two-qubit interaction terms such as \(Z_c \otimes X_t\), this operator means:

• apply \(Z\) to qubit \(c\),

• apply \(X\) to qubit \(t\),

• apply the identity to all remaining qubits.

3.1.5 Controllability properties↩︎

Inspired by [17], [47], [48], we are going to study the controllability properties of 13 . Note that, for the next proposition, the time horizon \(T>0\) is not fixed⁷.

The proof is going to be based on proving that \[\left\{-iH_0,-iX_1,-iY_1,\dots,-iX_k,-iY_k,\dots,-iX_n,-iY_n\right\}\] generates the Lie algebra \(su(N)=su(2^n)\) (which, by [17], implies controllability). The proof is made of two main steps

• Show controllability in each component⁸ of the state space \[\label{hragskno} \mathcal{H} = \underbrace{\mathbb{C}^2 \otimes \dots \otimes \mathbb{C}^2}_{127\text{ times}} = \mathbb{C}^{2^{127}}.\tag{15}\]

• Prove that the free dynamics hamiltonian \(H_0\) is able to couple the different components.

We are not going to employ the drift-Hamiltonian (\(H_0\)); this might be useful to reduce the number of control switches.

Before starting the proof, let us introduce some notation.

Notation for the proof

• We define the Lie algebra \[\mathscr{L}_0\overset{\scriptscriptstyle\mathrm{def}}{=}Lie algebra generated\left\{-iH_0,-iX_1,-iY_1,\dots,-iX_k,-iY_k,\dots,-iX_n,-iY_n\right\}\footnote{this is a Lie algebra with scalars in \mathbb{R}};\]

• Consider the multiples of the Pauli matrices \[\overline{\sigma}_x = \frac{i}{2}X = \frac{1}{2}\begin{pmatrix} 0 & i \\ i & 0 \end{pmatrix}, \quad \overline{\sigma}_y = -\frac{i}{2}Y = \frac{1}{2}\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}, \quad \overline{\sigma}_z = \frac{i}{2}Z = \frac{1}{2}\begin{pmatrix} i & 0 \\ 0 & -i \end{pmatrix}.\] This allows rewriting \[\mathscr{L}_0= Lie algebra generated\left\{-iH_0,\overline{\sigma}_{x,1},\overline{\sigma}_{y,1},\dots,\overline{\sigma}_{x,k},\overline{\sigma}_{y,k},\dots,\overline{\sigma}_{x,n},\overline{\sigma}_{y,n}\right\}.\]

• Define \(\overline{\sigma}_0\overset{\scriptscriptstyle\mathrm{def}}{=}I\).

• Let \(A\) be an arbitrary \(2\times 2\) matrix with complex entries and \(k\in \left\{1,\dots,n\right\}\). We define \[A_k \overset{\scriptscriptstyle\mathrm{def}}{=}I^{\otimes k-1} \otimes A \otimes I^{\otimes (127 - k)}=\underbrace{I \otimes \dots \otimes I}_{k-1\text{ times}}\otimes A \otimes \underbrace{I \otimes \dots \otimes I}_{127 - k\text{ times}}.\]

• Let \(A\) and \(B\) be two arbitrary \(2\times 2\) matrices with complex entries, \(k_1\in \left\{1,\dots,n\right\}\) and \(k_2\in \left\{1,\dots,n\right\}\), with \(k_1< k_2\). We define \[A_{k_1}B_{k_2} \overset{\scriptscriptstyle\mathrm{def}}{=}I^{\otimes k_1-1} \otimes A \otimes I^{\otimes (k_2 - k_1 - 1)} \otimes B \otimes I^{\otimes (127 - k_2)}=\underbrace{I \otimes \dots \otimes I}_{k_1-1\text{ times}}\otimes A \otimes \underbrace{I \otimes \dots \otimes I}_{k_2 - k_1 - 1\text{ times}} \otimes B \otimes \underbrace{I \otimes \dots \otimes I}_{127 - k_2\text{ times}}.\]

• Let \(A\) and \(B\) be two arbitrary \(2\times 2\) matrices with complex entries, \(k_1\in \left\{1,\dots,n\right\}\) and \(k_2\in \left\{1,\dots,n\right\}\), with \(k_1> k_2\). We define \[A_{k_1}B_{k_2} \overset{\scriptscriptstyle\mathrm{def}}{=}I^{\otimes k_1-1} \otimes B \otimes I^{\otimes (k_2 - k_1 - 1)} \otimes A \otimes I^{\otimes (127 - k_2)}=\underbrace{I \otimes \dots \otimes I}_{k_1-1\text{ times}}\otimes B \otimes \underbrace{I \otimes \dots \otimes I}_{k_2 - k_1 - 1\text{ times}} \otimes A \otimes \underbrace{I \otimes \dots \otimes I}_{127 - k_2\text{ times}}.\]

• Define the group \((\left\{0,x,y,z\right\},+)\), where \(x+y\overset{\scriptscriptstyle\mathrm{def}}{=}z\), \(y+z\overset{\scriptscriptstyle\mathrm{def}}{=}x\), \(z+x\overset{\scriptscriptstyle\mathrm{def}}{=}y\) and \(0\) is the neutral element⁹. All the operation on indices \(q\in \left\{0,x,y,z\right\}\) are intended in this group.

The above definition of the operation \(+\) in \(\left\{0,x,y,z\right\}\) is motivated by the following remark.

3.2 Proof of the Quantum Advantage for the Quantum Fourier Transform↩︎

In the introduction, we mentioned the Quantum Fourier Transform (QFT) as a central example of Quantum Advantage (QA). In this section, we rigorously verify that QA holds for the QFT within the control-theoretic framework of definition 2.3. The argument is based on two ingredients:

1. a gate concatenation lemma, which exploits the left-invariance of the bilinear Schrödinger equation;

2. the well-known decomposition of the QFT into \(O(n^2)\) elementary quantum gates (see, e.g. [1]).

3.2.1 Left-invariance and gate concatenation↩︎

The bilinear Schrödinger equation 3 is left-invariant: the dynamics depend on the controls but not on the current state \(U(t)\) in a way that favors any particular group element. We exploit this property to bound the minimal time for a composite unitary in terms of the minimal times for its factors.

By induction on lemma 3.1, we immediately obtain the following.

3.2.2 The Quantum Fourier Transform↩︎

The Quantum Fourier Transform (QFT) on \(n\) qubits is the unitary operator \(\Gamma_{\tiny{QFT}} \in SU(2^n)\) defined by its action on the computational basis vectors \(|k\rangle\), \(k \in \{0, 1, \dots, 2^n - 1\}\), as \[\label{QFT95definition} \Gamma_{\tiny{QFT}} |k\rangle = \frac{1}{\sqrt{2^n}} \sum_{l=0}^{2^n - 1} e^{2\pi i k l / 2^n} |l\rangle.\tag{38}\] Equivalently, in matrix form, \(\Gamma_{\tiny{QFT}}\) is the \(2^n \times 2^n\) unitary matrix with entries \[\left(\Gamma_{\tiny{QFT}}\right)_{l,k} = \frac{1}{\sqrt{2^n}} e^{2\pi i k l / 2^n}, k,l \in \{0, 1, \dots, 2^n - 1\}.\] It is well-known (see [1]) that the QFT can be decomposed into a product of elementary quantum gates as follows.

3.2.3 Quantum Advantage for the QFT↩︎

We now combine the gate concatenation result (corollary 3.1) with the QFT decomposition (proposition 3.2) to establish Quantum Advantage.

We require the following assumption on the physical hardware.

Combining theorem 3.1 with the necessary condition for QA (proposition 8.1), we obtain the following.

The above corollary provides a checkable necessary condition: if the value function \(V(T,\Gamma_{\tiny{QFT}})\) grows faster than \(O(n^2)\), then the assumption of uniformly bounded elementary gate time (definition 3.1) cannot hold for the given hardware.

4 Quantum Discrete Optimization: the Maximum Independent Set (MIS) problem↩︎

4.1 Introduction↩︎

The paradigm of Quantum Computing (QC) [1] is currently navigating the Noisy Intermediate-Scale Quantum (NISQ) era, an epoch characterized by hardware that possesses sufficient qubit counts to challenge classical supercomputers but lacks the fault-tolerant error correction required for deep, universal gate-based algorithms. Within this landscape, combinatorial optimization has emerged as a primary candidate for demonstrating practical quantum advantage. Among the most prominent algorithmic strategies is the Quantum Approximate Optimization Algorithm (QAOA) [49], [50], initially proposed as a digital, variational protocol designed to explore the Hilbert space of near-term processors to isolate the ground states of objective Hamiltonians.

In this chapter, rather than addressing general discrete optimization, we restrict ourselves to a single, paradigmatic problem: the Maximum Independent Set (MIS) problem on an undirected simple graph. The choice of MIS is not accidental:

• MIS is NP-hard [4] and admits a clean, minimal binary-variable formulation, requiring only one binary variable per vertex of the underlying graph;

• MIS is naturally encoded on neutral-atom quantum processors via the Rydberg blockade mechanism (chapter 4.3 and [5]–[7]), without any need to introduce artificial penalty terms;

• MIS, being a constrained combinatorial problem with a graph-theoretic structure, is particularly well suited to a control-theoretic analysis of the QAOA dynamics.

All along this chapter, we work exclusively with binary variables \(x_i \in \{0, 1\}\) (one per vertex), without recurring to the spin-variable change \(z_i = 1 - 2 x_i \in \{-1, +1\}\). Accordingly, the cost Hamiltonian is built directly from the qubit projector \(\hat{n}_i = |1\rangle\langle 1|_i = (I - Z_i)/2\), which is the natural quantum lift of the binary variable \(x_i\).

Historically, QAOA was conceived as a heuristic sequence of discrete unitary operations, alternating between a problem-specific Hamiltonian and a beginning Hamiltonian. However, as the physical limitations of discrete gate synthesis, such as accumulated Trotterization errors and gate fidelities, become increasingly apparent, the theoretical understanding of QAOA is undergoing a fundamental transformation. By casting the optimization problem into the continuous-time domain, QAOA can be rigorously reinterpreted through the mathematical lens of Quantum Optimal Control theory. This perspective bridges the gap between pure Adiabatic Quantum Optimization (AQO) and digital variational algorithms, revealing that QAOA is fundamentally a discretized approximation of a continuous “bang-anneal-bang” optimal control protocol [51].

This chapter is structured as follows. Section 4.2 introduces the MIS problem in the language of graph theory and recasts it as a Quadratic Unconstrained Binary Optimization (QUBO) problem. Subsection 4.3.5 promotes the binary cost function to a self-adjoint operator on \((\mathbb{C}^2)^{\otimes n}\), the so-called cost Hamiltonian, introduces the mixer Hamiltonian, and establishes the natural encoding of MIS on neutral-atom Pasqal-type hardware. In subsection 4.4.6, we show how that MIS can be solved successfully on Pasqal machines, in a sufficiently large time horizon \(T\). In section 4.5, we present estimates needed to prove Quantum Advantage. Section 4.6 outlines the classical-quantum hybrid loop. Finally, section 4.7 introduces an integral tracking functional that stabilizes the optimal control problem along the entire trajectory, suppressing diabatic leakage.

A closely related approach is Quantum Annealing. Rather than targeting universal computation, Quantum Annealing hardware is uniquely designed to solve discrete optimization problems. See, for instance, the recent paper [52] benchmarking Quantum Annealing and classical optimizers. Several companies are developing Quantum Annealing hardware, including D-WAVE. There exists already a robust interplay between Quantum Annealing and Control Theory (see, for instance, Annealing Implementation and Controls and [51], [53]).

4.2 The Maximum Independent Set problem↩︎

Let \(G = (V, E)\) be an undirected simple graph, with vertex set \(V = \{1, 2, \dots, n\}\) and edge set \[E \subseteq \big\{ \{i,j\} \;\big| \;i, j \in V, \;i \neq j \big\}.\]

4.2.1 Binary-variable formulation↩︎

Following the bijection between subsets of \(V\) and binary indicator vectors, we encode each \(S \subseteq V\) as \[\label{indicator95vector} \mathbf{x} = (x_1, \dots, x_n) \in \{0, 1\}^n, \quad x_i \mathrel{\vcenter{:}}= \begin{cases} 1 & ifi \in S, \\ 0 & ifi \notin S. \end{cases}\tag{44}\] Each component \(x_i\) is a binary variable taking values in \(\{0,1\}\). The independence constraint of definition 4.1 reads, in these variables, \[\label{indep95constraint} x_i \, x_j = 0, \quad \forall \, \{i, j\} \in E,\tag{45}\] since the two endpoints of an edge cannot both be selected. Define \[\label{cost95function} g(\mathbf{x})\mathrel{\vcenter{:}}= \sum_{i=1}^n x_i.\tag{46}\] Problem 42 is therefore equivalent to the constrained quadratic binary program \[\label{mis95constrained} \max_{\mathbf{x} \in \{0,1\}^n}g(\mathbf{x}) = \sum_{i=1}^n x_i, \quad subject to \quad x_i x_j = 0, \;\forall \{i,j\} \in E.\tag{47}\]

By introducing a penalty parameter \(\lambda > 1\), problem 47 can be recast as the unconstrained Quadratic Unconstrained Binary Optimization (QUBO) problem [54], [55]: \[\label{mis95qubo} \min_{\mathbf{x} \in \{0,1\}^n} f(\mathbf{x}), \qquad f(\mathbf{x}) \mathrel{\vcenter{:}}= -\sum_{i=1}^n x_i + \lambda \sum_{\{i,j\} \in E} x_i \, x_j.\tag{48}\] The cost \(f\) in 48 is purely quadratic in the binary variables \(x_i\), of the form \(\mathbf{x}^\top Q \mathbf{x}\) for a symmetric matrix \(Q \in \mathbb{R}^{n\times n}\) (recall \(x_i^2 = x_i\) for \(x_i \in \{0,1\}\), so the linear term may be absorbed into the diagonal of \(Q\)).

The cardinality of the search space \(\{0,1\}^n\) is \(2^n < +\infty\), ensuring the existence of a global minimizer (uniqueness, in general, might fail). However, locating \(\mathbf{x}_{\tiny{opt}}\) is NP-hard [4], [56], since MIS is one of Karp’s original 21 NP-complete problems.

4.3 Neutral-atom analog quantum computers↩︎

4.3.1 Introduction↩︎

Neutral-atom quantum computers manipulate spatial configurations of atoms, such as \({}^{87}\text{Rb}\) trapped in optical tweezer arrays, to perform quantum operations [5]. Information is encoded by assigning the logical state \(|0\rangle\) to the atom’s ground state and \(|1\rangle\) to a highly excited Rydberg state. By exposing these atoms to highly controlled laser pulses, the system undergoes a time evolution governed by the controlled Schrödinger equation. As illustrated in [5], neutral atoms quantum computers can operate either in digital mode or in analog mode. Digital mode is designed to program with discrete-time quantum gates and enjoys universal quantum computation capabilities, whereas analog mode is time-continuous and it is particularly suitable for discrete optimization. In these notes, we focus in the analog mode.

For a general introduction on Quantum Computing (QC), see [1].

4.3.2 The Controlled Schrödinger Equation↩︎

As in 2 , in the field of quantum control, the evolution of a quantum state \(|\psi(t)\rangle\) is often described by a bilinear controlled Schrödinger equation \[i\hbar \frac{d}{dt}\psi(t) = \left( H_0 + \sum_{k=1}^m u_k(t) H_k \right) \psi(t), \label{eq:boscain}\tag{49}\] where \(H_0\) is the unforced (drift) Hamiltonian representing the internal dynamics of the system, \(\{H_k\}_{k=1}^{m}\) are the interaction Hamiltonians, and \(\{u_k(t)\}_{k=1}^{m}\) are the real-valued, time-dependent control fields driving the system.

4.3.3 Application to the Pasqal Architecture↩︎

For a neutral-atom quantum processor like Pasqal’s Orion, the physical controls correspond to a two-photon laser transition scheme. The system is globally driven by fields parameterized by their Rabi frequency amplitude \(\Omega(t)\) and their detuning from the Rydberg transition resonance \(\delta(t)\), as in Pasqal documentation.

Inspired by [5], [57], the total Hamiltonian \(H(t)\) governing the atomic register of \(n\) qubits is given by: \[\label{neutral95atoms95hamiltonian} H(t) = \frac{\hbar \, \Omega(t)}{2} \sum_{k=1}^{n} X_k - \hbar \, \delta(t) \sum_{i=1}^{n} \hat{n}_i + \sum_{\substack{i,j=1 \\ i<j}}^{n} \frac{C_6}{R_{i,j}^6} \, \hat{n}_i \, \hat{n}_j,\tag{50}\] where

• as in chapter 2, the state space is the following Hilbert space over \(\mathbb{C}\)¹¹ \[\mathcal{H} \overset{\scriptscriptstyle\mathrm{def}}{=}\underbrace{\mathbb{C}^2 \otimes \dots \otimes \mathbb{C}^2}_{n\text{ times}} = \bigotimes_{j=1}^n \mathbb{C}^2;\]

• \(X_k=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}_k\) is the Pauli-\(X\) operator acting on qubit \(k\);

• \(\hat{n}_k = (I - Z_k)/2=\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}_k=|1\rangle\langle 1|_k\) is the Rydberg occupation number at site \(k\);

• \(C_6\in \mathbb{R}\) defines the van der Waals interaction strength;

• \(R_{i,j}\in (0,+\infty)\) is the spatial distance between atoms \(i\) and \(j\).

To map the Pasqal Hamiltonian 50 exactly to the control framework of 49 , we set \(m=2\) and define the terms as follows:

• Drift Hamiltonian (\(H_0\)): The constant van der Waals interactions between pairs of atoms, \[\label{drift95hamiltonian95pasqal} H_0 = \sum_{\substack{i,j=1 \\ i<j}}^{n} \frac{C_6}{R_{i,j}^6} \, \hat{n}_i \, \hat{n}_j.\tag{51}\]

• Control fields (\(u_1(t), u_2(t)\)): The time-dependent parameters dictated by the global laser fields, \[u_1(t) = \hbar \Omega(t), \quad u_2(t) = \hbar \delta(t).\]

• Control Hamiltonians (\(H_1, H_2\)): The operators coupling to the control fields, \[\label{control95hamiltonians95pasqal} H_1 = \frac{1}{2} \sum_{k=1}^{n} X_k, \quad H_2 = - \sum_{k=1}^{n} \hat{n}_k.\tag{52}\]

Substituting these definitions back into the general controlled Schrödinger equation yields the exact time-evolution equation for the neutral-atom register: \[\label{pasqal95equation95explicit} i\hbar \frac{d}{dt}\psi(t) = \left( \sum_{\substack{i,j=1 \\ i<j}}^{n} \frac{C_6}{R_{i,j}^6} \hat{n}_i \hat{n}_j + \hbar \Omega(t) \left[ \frac{1}{2}\sum_{k=1}^{n}X_k \right] - \hbar \delta(t) \left[ \sum_{k=1}^{n}\hat{n}_k \right] \right) \psi(t).\tag{53}\]

As we shall see, with respect to superconducting quantum computers studied in section 3.1, neutral atoms quantum computers (in analog mode)

• have weaker controllability property (they are not universal quantum computers);

• enjoys a better connectivity.

4.3.4 Controllability properties of the neutral-atom register↩︎

In contrast with the superconducting setting of chapter 3, the Pasqal bilinear Schrödinger equation 53 is driven by only two global scalar controls \(\Omega(t)\) and \(\delta(t)\), which act uniformly on all the qubits (through \(H_1 = \tfrac{1}{2}\sum_{k=1}^{n} X_k\) and \(H_2 = -\sum_{k=1}^{n} \hat{n}_k\)). A direct consequence is that the reachable set of 53 is much smaller than \(SU(2^n)\): indeed, every symmetry of the drift \(H_0\) in 51 that also commutes with \(H_1\) and \(H_2\) is automatically conserved by the dynamics. Similar controllability results were proved in [53].

We highlight that, as we mentioned, the above result holds for Pasqal devices in analog mode. Pasqal devices in digital model are Universal Quantum Computers (operator controllability holds). In these notes, we focus on analog mode.

Proposition 4.2 is not a pathology: it reflects the fact that the neutral-atom platform considered here is an analog quantum simulator tailored to a specific class of Hamiltonian problems (Ising/Rydberg-type), rather than a universal digital quantum computer. The appropriate notion of controllability in this setting is not full operator controllability on \(SU(2^n)\), but rather the weaker property of being able to steer, in polynomial time in \(n\), the initial state \(\phi_B=|0\rangle^{\otimes n}\) to a ground state of the MIS cost Hamiltonian (see Proposition [prop_mis_hamiltonian] and section 4.4). Since \(\phi_B=|0\rangle^{\otimes n}\) is precisely the ground state of \(H_{\gamma}(0)=H_{0}+\hbar\delta_{0}\sum_{k=1}^{n}\hat{n}_{k}\) (Lemma 4.3(a)), this steering is realised by the adiabatic programme of [58]: slowly deform \(H_{\gamma}(0)\) into \(H_{\gamma}(1)\), whose ground manifold encodes the MIS (Lemma 4.3(b)). This is the control-theoretic content of the quantum-annealing programme of [51] and will be formulated precisely in section 4.4.

4.3.5 Natural encoding on neutral-atom hardware↩︎

Typically, Quantum Computers (QC) are efficient at solving problems whose input and output are discrete, while the intermediate computation is continuous. In this spirit, MIS is solved on a quantum computer by continuous-time methods: Quantum Annealing [58], [59] and the Quantum Approximate Optimization Algorithm (QAOA) [49], [50]. In [51], both are interpreted within the unifying framework of quantum optimal control.

We now show how MIS can be encoded in the physics of the neutral-atom Pasqal Quantum Computers, through an appropriate spatial configuration of the atoms. Take the Hamiltonian 50 , with controls \((\Omega,\delta)\equiv (0,1)\), getting \[\label{cost95hamiltinian43remainder} H_C\mathrel{\vcenter{:}}= - \hbar \sum_{i=1}^{n} \hat{n}_i + \sum_{\substack{i,j=1 \\ i<j}}^{n} \frac{C_6}{R_{i,j}^6} \, \hat{n}_i \, \hat{n}_j,\tag{54}\] Roughly speaking, appropriately positioning the atoms realizing the qubits, \(H_C\) represents 48 , up to a tail energy.

The key physical consequence is that when the van der Waals coupling dominates the Rabi frequency, \(C_6/R_b^6 \gg \hbar\Omega_{\max}\) (the Rydberg-blockade regime), the doubly-excited state \(|11\rangle_{ij}\) on any edge \(\{i,j\}\in E\) is energetically forbidden during the evolution. The drift Hamiltonian thereby enforces the independence constraint 45 by physics, not by software, with an effective penalty parameter \(\lambda_{\tiny{eff}} \sim C_6 / (R_b^6 \, \hbar \Omega_{\max})\).

4.4 Exact state controllability and the QAOA optimal control formulation↩︎

In section 4.3.5, we established that the Rydberg blockade naturally enforces the independence constraint (Proposition 4.3). We take as initial state the all-zero computational state \[\label{initial95state95phiB} \phi_B = |0\rangle^{\otimes n} = |\mathbf{0}\rangle .\tag{58}\] In the standard Quantum Approximate Optimization Algorithm (QAOA) [49] one initialises in the uniform superposition \(|+\rangle^{\otimes n}\), the ground state of the transverse-field mixer. Here, however, the controlled Hamiltonian is the Pasqal Hamiltonian 50 , and a different choice is more natural: by Lemma 4.3(a), \(\phi_B=|0\rangle^{\otimes n}\) is the unique ground state of \[\label{endpoint95H095intro} H_{\gamma}(0)=H_{0}+\hbar\delta_{0}\sum_{k=1}^{n}\hat{n}_{k},\tag{59}\] the Pasqal Hamiltonian at the control endpoint \((\Omega,\delta)=(0,-\delta_0)\), with spectral gap \(\hbar\delta_0>0\) above it. Starting in \(\phi_B=|0\rangle^{\otimes n}\) therefore means starting in a known, gapped ground state, and slowly moving to the ground state of \(H_{\gamma}(1)\), which encodes solutions of MIS by Lemma 4.3(b), realises the adiabatic approach of [58], to which we append a final closed-orbit argument promoting approximate to exact controllability.

The central question of this section is:

The analysis is carried out entirely on the physical Pasqal Hamiltonian 50 , without passing through any abstract interpolating Hamiltonian. As we shall show, the answer involves three ingredients: a symmetry obstruction identifying the correct target (the MIS subspace \(\mathcal{H}_{\mathrm{MIS}}\)), an adiabatic anneal on \((\Omega,\delta)\) in the spirit of [58], and a Lie-group compactness argument promoting approximate reachability to exact reachability.

4.4.1 The QAOA optimal control problem↩︎

Following [51], we formulate the state-preparation task as a continuous-time optimal control problem. Given a time horizon \(T>0\), the QAOA optimal control problem reads \[\label{optimal95control95problem95qaoa} \min_{\Omega,\,\delta\in \mathscr{U}_{\mathrm{ad}}^T} \; J_T(\Omega,\delta) \;\mathrel{\vcenter{:}}=\; \langle \psi(T) | H_C | \psi(T) \rangle,\tag{60}\] subject to the state equation, driven by the Pasqal Hamiltonian 50 , \[\label{QAOA95state95equation} \begin{cases} \displaystyle i\hbar \frac{d}{dt}\psi(t) = \left(\frac{\hbar\,\Omega(t)}{2}\sum_{k=1}^n X_k - \hbar\,\delta(t)\sum_{k=1}^n\hat{n}_k + \sum_{\substack{i,j=1\\i<j}}^{n}\frac{C_6}{R_{i,j}^6}\,\hat{n}_i\hat{n}_j\right)\psi(t), & t\in(0,T),\\[6pt] \psi(0) = \phi_B = |0\rangle^{\otimes n}, \end{cases}\tag{61}\] with admissible controls \[\label{admissible95controls95pasqal} \mathscr{U}_{\mathrm{ad}}^T \;\mathrel{\vcenter{:}}=\; \big\{(\Omega,\delta)\in L^\infty(0,T;\mathbb{R}^2) \;\big|\; \Omega(t)\in [0,\Omega_{\max}],\; \delta(t)\in [-\delta_{\max},\delta_{\max}],\;a.e. t\in(0,T)\big\}.\tag{62}\]

4.4.2 Symmetry obstruction to reaching a single \(|\mathbf{x}^{*}\rangle\)↩︎

4.4.3 The MIS subspace as relaxed target↩︎

By Proposition 4.4, no single computational-basis state \(|\mathbf{x}^{*}\rangle\) encoding a maximum independent set is reachable from \(\phi_B\) as soon as some \(\sigma\in\mathrm{Aut}(G,w)\) moves \(\mathbf{x}^{*}\). We therefore relax the target from an individual optimal bitstring to the whole subspace it spans. Let \[\label{mis95set95def} \mathrm{MIS}(G)\mathrel{\vcenter{:}}=\{\mathbf{x}\in\{0,1\}^n : \mathbf{x} encodes an MIS of G\},\qquad d\mathrel{\vcenter{:}}=|\mathrm{MIS}(G)|,\tag{63}\] and define the MIS subspace \[\label{mis95subspace95def} \mathcal{H}_{\mathrm{MIS}}\;\overset{\scriptscriptstyle\mathrm{def}}{=}\;\mathop{\mathrm{span}}_{\mathbb{C}}\bigl\{|\mathbf{x}\rangle:\mathbf{x}\in\mathrm{MIS}(G)\bigr\},\qquad \dim\mathcal{H}_{\mathrm{MIS}}=d .\tag{64}\]

Relaxed goal. Reach a state from which a computational-basis measurement returns a maximum independent set with certainty; that is, steer the system to \[\label{relaxed95goal} \psi(T)\in\mathcal{H}_{\mathrm{MIS}}\qquad\Longleftrightarrow\qquad \bigl\|P_{\mathcal{H}_{\mathrm{MIS}}}\,\psi(T)\bigr\|=1 ,\tag{65}\] where \(P_{\mathcal{H}_{\mathrm{MIS}}}:\mathcal{H}\to\mathcal{H}_{\mathrm{MIS}}\) denotes the orthogonal projection onto \(\mathcal{H}_{\mathrm{MIS}}\). Indeed, since \(\{|\mathbf{y}\rangle:\mathbf{y}\in\mathrm{MIS}(G)\}\) is an orthonormal basis of \(\mathcal{H}_{\mathrm{MIS}}\), the Born rule gives, for any normalised \(\psi\), \[\label{measurement95MIS95certainty} \mathbb{P}\big[\mathbf{x} encodes an MIS of G\big] = \sum_{\mathbf{y}\in\mathrm{MIS}(G)}\big|\langle\mathbf{y}|\psi\rangle\big|^2 = \bigl\|P_{\mathcal{H}_{\mathrm{MIS}}}\psi\bigr\|^2 ,\tag{66}\] so the success probability equals \(1\) precisely when \(\psi\in\mathcal{H}_{\mathrm{MIS}}\). The relaxed target is thus the affine sphere \(S(\mathcal{H}_{\mathrm{MIS}})=\{\psi\in\mathcal{H}_{\mathrm{MIS}}:\|\psi\|=1\}\), an entire manifold rather than a single point, and it is compatible with the symmetry constraint of Proposition 4.4, because \(\mathrm{Aut}(G,w)\) permutes \(\mathrm{MIS}(G)\) and hence preserves \(\mathcal{H}_{\mathrm{MIS}}\).

A distinguished element of \(S(\mathcal{H}_{\mathrm{MIS}})\) is the symmetry-adapted MIS state \[\label{symmetry95adapted95MIS} \psi_{\mathrm{MIS}} \;\mathrel{\vcenter{:}}=\; \frac{1}{\sqrt{d}}\sum_{\mathbf{x}\in\mathrm{MIS}(G)} |\mathbf{x}\rangle\;\in\;\mathcal{H}_{\mathrm{MIS}}\cap\mathcal{H}^{\mathrm{Aut}(G,w)},\tag{67}\] the uniform superposition over all maximum independent sets, which is \(P_\sigma\)-invariant for every \(\sigma\in\mathrm{Aut}(G,w)\). We keep \(\psi_{\mathrm{MIS}}\) only as a convenient representative (for instance in the unique-MIS Corollary 4.3): the protocol below is not required to reach this particular vector, only to reach the subspace \(\mathcal{H}_{\mathrm{MIS}}\).

4.4.4 The dynamical Lie algebra and closedness of the orbit↩︎

4.4.5 Spectral gap of the Pasqal Hamiltonian along a control path↩︎

We define the spectral gap directly for the Pasqal Hamiltonian 50 , parametrized by the controls \((\Omega,\delta)\).

A natural choice of adiabatic control path is the bell-shaped schedule: \[\label{bell95schedule} \Omega(s) = \Omega_{\max} 4s(1-s),\qquad \delta(s) = \delta_0(2s-1),\qquad s\in[0,1].\tag{75}\] At \(s=0\): \((\Omega,\delta)=(0,-\delta_0)\); at \(s=1/2\): \((\Omega,\delta)=(\Omega_{\max},0)\); at \(s=1\): \((\Omega,\delta)=(0,+\delta_0)\).

Notation for the endpoint analysis. Throughout, \(H_{\gamma}\) denotes the instantaneous Pasqal Hamiltonian \(H_{\gamma}(s)\) along the control path \(\gamma\), defined in 73 ; we write \(\lvert\mathbf{x}\rvert\overset{\scriptscriptstyle\mathrm{def}}{=}\sum_{k=1}^{n}x_{k}\) for the Hamming weight of \(\mathbf{x}\in\{0,1\}^{n}\) (the cardinality of the encoded subset), with \(\mathbf{0}\) the all-zero string, \(\lvert\mathbf{0}\rangle=\lvert0\rangle^{\otimes n}\). Under the physical convention \(C_{6}>0\) (repulsive Rydberg interaction), the couplings \(J_{ij}\overset{\scriptscriptstyle\mathrm{def}}{=}C_{6}/R_{i,j}^{6}>0\) make \(H_{0}\) diagonal in the computational basis, with \[\langle\mathbf{x}\rvert H_{0}\lvert\mathbf{x}\rangle=\sum_{\substack{i,j=1 \\ i<j}}^{n}J_{ij}x_{i}x_{j}\ge0\] by ?? ; we set the blockade scale \[\label{loc:blo} J_{\mathrm{blo}}\overset{\scriptscriptstyle\mathrm{def}}{=}\frac{C_{6}}{R_{b}^{6}}>0 .\tag{76}\] At the endpoints 72 , the operators \[\label{loc:endpoints} H_{\gamma}(0)=H_{0}+\hbar\delta_{0}\sum_{k=1}^{n}\hat{n}_{k}, \qquad H_{\gamma}(1)=H_{0}-\hbar\delta_{0}\sum_{k=1}^{n}\hat{n}_{k}\tag{77}\] are diagonal in the computational basis (sums of diagonal operators), with eigenpairs \(\bigl(E_{a}(\mathbf{x}),\lvert\mathbf{x}\rangle\bigr)\) and \(\bigl(E_{b}(\mathbf{x}),\lvert\mathbf{x}\rangle\bigr)\), where \[\label{loc:Ea} E_{a}(\mathbf{x})\overset{\scriptscriptstyle\mathrm{def}}{=}\langle\mathbf{x}\rvert H_{0}\lvert\mathbf{x}\rangle+\hbar\delta_{0}\,\lvert\mathbf{x}\rvert,\tag{78}\] \[\label{loc:Eb} E_{b}(\mathbf{x})\overset{\scriptscriptstyle\mathrm{def}}{=}\langle\mathbf{x}\rvert H_{0}\lvert\mathbf{x}\rangle-\hbar\delta_{0}\,\lvert\mathbf{x}\rvert .\tag{79}\] For \(\mathbf{x}\) encoding an independent set, ?? gives \(\langle\mathbf{x}\rvert H_{0}\lvert\mathbf{x}\rangle=\tau(\mathbf{x})\), where the tail energy is \[\label{loc:tail} \tau(\mathbf{x})\overset{\scriptscriptstyle\mathrm{def}}{=}\!\!\sum_{\substack{\{i,j\}\notin E\\ i<j}}\!\! J_{ij}\,x_{i}x_{j}\;=\!\!\sum_{\substack{\{i,j\}\notin E\\ i<j}}\!\! \frac{C_{6}}{R_{i,j}^{6}}\,x_{i}x_{j}\;\ge 0,\tag{80}\] while ?? gives \(\langle\mathbf{x}\rvert H_{0}\lvert\mathbf{x}\rangle\ge J_{\mathrm{blo}}\) for any \(\mathbf{x}\) violating independence. We abbreviate the worst-case tail over independent sets by \[\label{loc:taumax} \tau^{\max}\overset{\scriptscriptstyle\mathrm{def}}{=}\max\bigl\{\tau(\mathbf{x})\;:\;\mathbf{x}\in\{0,1\}^{n}\;\text{independent}\bigr\}\;\ge 0 .\tag{81}\] Finally, \(\mathcal{H}_{\mathrm{IS}}\overset{\scriptscriptstyle\mathrm{def}}{=}\mathop{\mathrm{span}}\{\lvert\mathbf{x}\rangle:\mathbf{x}\text{ encodes an independent set}\}\) is the independent-set subspace of Corollary 4.1.

Define the energy-scale window as the conditions \[\label{energy95window}\tau^{\max}\;<\;\hbar\delta_{0} \qquad\text{and}\qquad \hbar\delta_{0}\,n+\tau^{\max}\;<\;J_{\mathrm{blo}}=\frac{C_{6}}{R_{b}^{6}} .\tag{82}\] In Lemma 4.2, we shall see under which conditions 82 is nonempty and, in Corollary 4.2, we will see 82 as a two-sided bound on the detuning amplitude \(\delta_0\).

4.4.6 Main result: exact reachability of \(\mathcal{H}_{\mathrm{MIS}}\) via an adiabatic anneal↩︎

Since \(\phi_B=|0\rangle^{\otimes n}\) is, by Lemma 4.3(a), the unique ground state of the Pasqal Hamiltonian \(H_\gamma(0)\) at the control endpoint \((\Omega,\delta)=(0,-\delta_0)\), no preliminary state-preparation (“reach”) phase is required: the protocol consists of a single adiabatic sweep of the physical Pasqal Hamiltonian 50 .

Adiabatic anneal.

Starting from \(\phi_B=|0\rangle^{\otimes n}\), the ground state of \(H_\gamma(0)\) (Lemma 4.3(a)), slowly sweep \((\Omega(t),\delta(t))\) along the adiabatic control path \(\gamma\) from \((0,-\delta_0)\) to \((0,+\delta_0)\), with time rescaling \(s=t/T_{\mathrm{anneal}}\). This is exactly the adiabatic-evolution scheme of [58]: the instantaneous ground state is tracked from \(H_\gamma(0)\) to \(H_\gamma(1)\), whose ground manifold is contained in the MIS subspace \(\mathcal{H}_{\mathrm{MIS}}\) (Lemma 4.3(b)). To this approximate scheme we append a closed-orbit argument (Proposition 4.7) that upgrades it to exact controllability into \(\mathcal{H}_{\mathrm{MIS}}\).

4.5 Is there quantum advantage for MIS?↩︎

Definition 2.3 of Quantum Advantage (QA) was formulated for operator controllability on \(SU(2^n)\), which, by Proposition 4.2, does not hold for the global, symmetric Pasqal controls. A meaningful notion of QA for the MIS problem on neutral-atom hardware therefore calls for a state-oriented adaptation of Definition 2.3, organized around three changes:

• the target is the ground-state manifold \(\mathcal{H}_{\mathrm{MIS}}\) of 64 rather than a single unitary \(\Gamma\in SU(2^n)\);

• success is the exact preparation of a state in \(\mathcal{H}_{\mathrm{MIS}}\) (equivalently, the sampling of a maximum independent set with certainty);

• the polynomial-time requirement is, intrinsically, a statement about a family of instances indexed by the number of vertices \(n\), not about a single graph.

For a normalised state \(\psi\in\mathcal{H}\), the probability that a computational-basis measurement returns a maximum independent set of \(G\) is, by the Born rule 66 , \[\label{mis95success95probability} \mathbb{P}_{\mathrm{MIS}}(\psi)\;=\;\bigl\|P_{\mathcal{H}_{\mathrm{MIS}}}\,\psi\bigr\|^{2}\;=\;\sum_{\mathbf{x}\in\operatorname{MIS}(G)}\bigl|\langle\mathbf{x}|\psi\rangle\bigr|^{2},\tag{103}\] and \(\mathbb{P}_{\mathrm{MIS}}(\psi)=1\) if and only if \(\psi\in\mathcal{H}_{\mathrm{MIS}}\). Accordingly we take as success event the exact membership \(\psi(T)\in\mathcal{H}_{\mathrm{MIS}}\), equivalently, the sampling of a maximum independent set with certainty, and define the minimal MIS-preparation time of \(G\) by \[\label{def95min95time95MIS} T_{\mathrm{MIS}}(G)\;\overset{\scriptscriptstyle\mathrm{def}}{=}\;\inf\Bigl\{T>0 \;\Big|\; \exists\,(\Omega,\delta)\in\mathscr{U}_{\mathrm{ad}}^{T}\;\text{such that}\;\psi(T)\in\mathcal{H}_{\mathrm{MIS}}\Bigr\}\footnote{we adopt the convention \inf\varnothing = + \infty},\tag{104}\] where \(\psi(\cdot)\) solves the Pasqal equation 53 with initial condition \(\psi(0)=\phi_B=|0\rangle^{\otimes n}\) and controls \((\Omega,\delta)\) in the admissible set \(\mathscr{U}_{\mathrm{ad}}^{T}\) 62 . This is the state-oriented analog of the operator minimal time 8 , the target operator \(\Gamma\) being replaced by the target subspace \(\mathcal{H}_{\mathrm{MIS}}\).

Remind the definition of the cost hamiltonian 54 and Lemma 4.3(b). Definitions 4.5–4.6 differ from Definition 2.3 in three respects:

1. Target. The target is not a unitary operator \(\Gamma\) on the whole of \(SU(2^n)\) but the ground-state manifold of \(H_C\), namely the MIS subspace \(\mathcal{H}_{\mathrm{MIS}}\) of 64 ; the relevant notion is state controllability (steering the fixed initial state \(\phi_B\) exactly into \(\mathcal{H}_{\mathrm{MIS}}\)) rather than operator controllability (implementing an arbitrary unitary).

2. Figure of merit. Success is the exact membership \(\psi(T)\in\mathcal{H}_{\mathrm{MIS}}\), equivalently \(\mathbb{P}_{\mathrm{MIS}}(\psi(T))=\|P_{\mathcal{H}_{\mathrm{MIS}}}\psi(T)\|^{2}=1\) by 103 : a single computational-basis measurement returns a maximum independent set with certainty.

3. Asymptotic object. The polynomial-time bound is meaningful only along a family of instances indexed by \(n\) (Definition 4.5); the worst-case notion (Definition 4.6) quantifies over all such families uniformly.

Proposition 4.8 shows that, under the widely believed complexity-theoretic assumption \(\mathsf{NP}\not\subseteq \mathsf{BQP}\), one cannot hope for a worst-case, exact QA in the sense of Definition 4.6. Three relaxations, each of independent interest from the control-theoretic viewpoint, are nevertheless meaningful and compatible with known complexity.

1. Average-case QA. Replace the worst-case requirement over all unit-disk graphs in Definition 4.6 by an expectation over a random ensemble. Specifically, let \(\mathcal{G}(n,\rho)\) denote the random geometric graph model in which \(n\) points are drawn uniformly in \([0,1]^2\) and two vertices are connected if and only if their Euclidean distance is at most \(\rho = \rho(n)\). Average-case QA holds if \[\label{average95case95QA} \mathbb{E}_{G\sim\mathcal{G}(n,\rho)}\big[\mathbb{P}[\mathbf{x} encodes an MIS of G]\big] \geq \eta\tag{108}\] for some \(\eta>0\) independent of \(n\), with a time horizon polynomial in \(n\). Numerical evidence in [7], [57] suggests that, on classes of random graphs at the hard-instance density, the Pasqal/QuEra platforms do sample near-optimal independent sets in time polynomial in \(n\) with non-trivial probability.

2. Approximate QA. Relax “Maximum Independent Set” in 106 to an approximation guarantee: for some fixed \(\varepsilon\in(0,1)\) (independent of \(n\) and \(G\)), require \[\label{approximate95QA} \mathbb{P}\big[\,\mathbf{x} encodes an independent set of G of cardinality \geq (1-\varepsilon)\,\alpha(G)\,\big]\geq \eta.\tag{109}\] This is the natural formulation in the QAOA literature, yielding an approximation-ratio guarantee rather than exact optimality. The computational complexity landscape changes significantly: whereas MIS is NP-hard to approximate within a factor \(n^{1-\varepsilon}\) in general [66], on unit-disk graphs a Polynomial Time Approximation Scheme (PTAS) exists classically [67], so the relevant question becomes whether the quantum protocol achieves a given approximation ratio faster than classical algorithms.

3. Turnpike QA. Replace the time bound \(T_G\leq C n^p\) by a polynomial upper bound on the minimal time of the integral-tracking optimal control problem 110 , in which the running cost \(\langle\psi(t)|H_C|\psi(t)\rangle\) enforces adiabatic following of the instantaneous ground state along the whole interval \([0,T]\).

The three relaxations (R1)–(R3) outline three research programmes, along which the control-theoretic machinery of chapter 8 (the surrogate commutator functional, Proposition 8.1) can be applied to test, necessarily or sufficiently, whether Quantum Advantage for MIS holds on a given class of instances.

4.6 The classical-quantum hybrid loop↩︎

The optimal control problem 60 61 is solved by interlacing classical and quantum computation, as follows.

• On the Quantum Computer (QC) one runs functional evaluation: the Schrödinger equation 61 is physically observed (not classically simulated). In practice, given a candidate control \(u(\cdot)\), the Quantum Computer prepares \(\psi(T)\) and a finite number of repeated measurements in the computational basis estimate \(J_T(u) = \langle \psi(T) | H_C | \psi(T) \rangle\) via the empirical average of \(f(\mathbf{x})\) over the sampled bitstrings.

• On the classical computer, one performs the optimization step (control update); for instance, by gradient descent with finite-difference gradients, by Bayesian optimization, or by trust-region methods.

For instance, in [57], QAOA on MIS instances is run

• on the quantum hardware Pasqal FRESNEL;

• using a Bayesian optimizer as the classical outer loop.

The Hamiltonian, of the form 50 , is written in [57], with controls \(\Omega_{\theta}(t)\) and \(\delta_{\theta}(t)\).

4.7 Stabilization via integral tracking functionals↩︎

The standard optimal control formulation 60 61 is inherently fragile, since the cost functional \(J_T(u)\) is evaluated only at the terminal time \(T\). If the system undergoes a diabatic transition at an intermediate time \(t < T\), due, e.g., to thermal noise or to a rapidly closing energy gap, the state \(\psi(t)\) may diverge from the instantaneous ground-state manifold of \(H_{\gamma}(t)\). Because the optimizer only receives a penalty at the terminal time, the gradient signal used to correct intermediate errors is highly diffuse.

To resolve this fragility and dynamically stabilize the system, advanced control theory modifies the QAOA objective by introducing an integral tracking functional. Instead of measuring only terminal performance, the target objective tracks the expected energy of \(H_C\) continuously throughout the entire evolution: \[\label{optimal95control95problem95qaoa95tracking} \min_{u \in L^2(0,T;\mathbb{R})} J_T(u) = \frac{\lambda_{\tiny{ctrl}}}{2} \int_0^T |u(t)|^2 dt + \frac{1}{2} \int_0^T \langle \psi(t) | H_C | \psi(t) \rangle dt,\tag{110}\] with state equation 61 and \(\lambda_{\tiny{ctrl}} > 0\) a regularization parameter (not to be confused with the QUBO penalty \(\lambda\) of 48 ). The Quantum Adiabatic Theorem implies that the optimal solution of 110 drives the system toward a ground state of \(H_C\), encoding a Maximum Independent Set of \(G\) (Lemma 4.3).

The mathematical lineage of this approach is rooted in classical PDE stabilization and turnpike theory [68]–[73]: the running cost \(\langle \psi | H_C | \psi \rangle\) plays the role of a tracking term penalizing deviations from the target ground-state manifold over the whole horizon \([0,T]\), while the \(L^2\) Tikhonov term ensures coercivity of the cost in the control variable.

5 Open problems↩︎

Let us present some interesting open problems, which, as long as we know, were not investigated in the literature so far.

1. Continuous-time direct proof of Quantum Advantage for QFT. Direct proof of the Quantum Advantage for QFT, not passing by discrete-time gates composition; rather employing explicit continuous-time controls. Of course, this might be relaxed to an approximate controllability result, where the QFT operator is reached, up to an error \(\varepsilon\).

2. Return time estimate. Estimate the minimal time \(T>0\) to solve the return problem \[\label{label95return95problem} \begin{cases} i\frac{d}{dt}U(t) = \big(H_0 + \sum_{j=1}^{m}u_j(t)H_j\big)U(t),& t\in (0,T)\\ U(0)=I,\\ U(T)=I.\\ \end{cases}\tag{111}\]

3. Stabilization along operators orbits. In the framework of section 2, does there exists a control \(u\in \mathscr{U}^T\), such that \[\int_{0}^{+\infty}\left\|U(t)-\exp(-iH_0t)\Gamma\right\|^2dt<+\infty\] ? This might be related to [24] and the possibility of moving in the manifold \(M=\left\{\exp(-iH_0t) \;| \;t\in \mathbb{R}\right\}\) in small time (smaller than the period of \(H_0\) if \(H_0\) is periodic).

4. Rigorous proof of uniformly bounded elementary gate time. In theorem 3.1, we assumed uniformly bounded elementary gate time (definition 3.1). A rigorous proof would require analyzing the minimal time for elementary gates (Hadamard, controlled-rotation, CNOT) in the presence of the drift Hamiltonian \(H_0\), showing that \(T_{\tiny{min}}(G) \leq \tau\) with \(\tau\) independent of \(n\). This likely involves a careful analysis in the interaction picture (rotating frame), exploiting the local structure of single- and two-qubit control Hamiltonians. A sub-Riemannian geometry viewpoint on \(SU(N)\) might be useful [16], [38].

5. Converse of the necessary condition for QA. Proposition 8.1 provides a necessary condition for QA in terms of the value function \(V(T,\Gamma)\). A natural question is whether the converse holds, namely: if \(V(T,\Gamma) \leq Cn^p\) for all \(T > 0\), does Quantum Advantage hold? This would provide a full characterization of QA in terms of the surrogate problem.

6. Greedy approach to minimize quantum hardware use in Quantum Computing. On the one hand, use quantum hardware is expensive. On the other hand, several real world problems (e.g., optimization problems) depends on continuously changing configurations. This would oblige to use quantum hardware in real-time, which would lead to huge licensing cost. Greedy approach [74]–[76] might be employed to

   • Identify the most representative configurations.

   • Compute solutions, by quantum hardware, offline only for the identified most representative configurations.

   • Compute solutions, for any configuration, online by combining pre-computed solutions.

   See also the work [77] on the transfer of knowledge in quantum algorithms.

7. New ansätze for quantum-powered discrete optimization. In the context of quantum discrete optimization (section 4), research new ansätze (controlled hamiltonians, fitting with given quantum hardware), maximizing controllability properties of the associated controlled Schrödinger equation to rapidly converge to the solution of the discrete optimization problem. Note that \[QAOAs \subset VQAs,\] where

   • QAOAs stands for Quantum Approximate Optimization Algorithms;

   • VQAs stands Variational Quantum Algorithms, like the Variational Quantum Eigensolver.

   From a terminological viewpoint, algorithms employing an ansatz, differing from the standard QAOA, would be named VQAs. New ansätze might employ controls to circumvent exponentially small gaps between first and second eigenvalues ofn the Hamiltonians.

Acronyms↩︎

For the reader’s convenience we collect here, in alphabetical order, all the acronyms employed throughout these notes, together with a short gloss tying each one to the control-theoretic framework developed in the sequel. The complexity-theoretic classes are mentioned below with their meaning (see, e.g., [1] and the references therein).

AQO

Adiabatic Quantum Optimization: the analog paradigm in which the register is driven by an Hamiltonian, slowly varying from an initial Hamiltonian to a problem Hamiltonian, to solve a discrete optimization problem.

BQP

Bounded-error Quantum Polynomial time: the class of decision problems solvable by a quantum computer in time polynomial in the input size with error probability at most \(1/3\). The working hypothesis \(\mathsf{NP}\not\subseteq\mathsf{BQP}\) underlies the worst-case obstruction to Quantum Advantage for the MIS problem.

CNOT

Controlled-NOT gate: the two-qubit entangling gate which, together with the single-qubit rotations, generates a universal gate set.

DFT

Discrete Fourier Transform on \(N=2^n\) points; classically computed in \(O(N\log N)\) operations by the FFT.

DMCV

Direct Methods in the Calculus of Variations [37]: used to establish existence of minimizers of the surrogate functional \(J_T\) and attainment of the minimal time \(T_{\tiny{min}}\) under the control constraint \(|u(t)|\le M\).

FFT

Fast Fourier Transform: the classical \(O(N\log N)\) algorithm computing the DFT, against which the \(O(n^2)\) cost of the QFT is to be compared.

IS

Independent Set: a subset of pairwise non-adjacent vertices of a graph \(G=(V,E)\); the associated subspace of the Hilbert space is denoted \(\mathcal{H}_{\mathrm{IS}}\).

MIS

Maximum Independent Set: an independent set of maximum cardinality \(\alpha(G)\); the family of maximizers is \(\operatorname{MIS}(G)\) and the corresponding subspace is \(\mathcal{H}_{\mathrm{MIS}}\). Computing \(\alpha(G)\) is NP-hard [4], and the problem admits a native neutral-atom encoding via the Rydberg blockade.

NISQ

Noisy Intermediate-Scale Quantum (era / devices): present-day hardware with a limited number of qubits and no full fault tolerance, the regime in which QAOA operates.

NP

Nondeterministic Polynomial time; NP-hard and NP-complete denote the corresponding hardness notions. Deciding a maximum independent set is NP-hard in the classical sense.

P

(deterministic) Polynomial time: the class of decision problems solvable by a classical deterministic machine in polynomial time.

PDE

Partial Differential Equation; the controlled Schrödinger equation is a PDE, in case the quantum state space \(\mathcal{H}\) has dimension infinity.

PTAS

Polynomial-Time Approximation Scheme: on unit-disk graphs the MIS problem admits a classical PTAS [67], which tempers the prospects for a worst-case Quantum Advantage.

QA

Quantum Advantage: in the sense of Definition 2.3, the conjunction of operator controllability (\(\mathscr{U}_{\tiny{ad}}\neq\varnothing\)) with a polynomial-in-\(n\) bound \(T_{\tiny{min}}\le Cn^p\) on the minimal control time. For discrete optimization problems, like Maximum Independent Set (MIS), the definition of Quantum Advantage is state-oriented (see Definition 4.5 and Definition 4.6).

QAOA

Quantum Approximate Optimization Algorithm [49]: here recast as a continuous-time bilinear optimal control problem.

QC

Quantum Computing / Quantum Computer.

QFT

Quantum Fourier Transform: the unitary \(\Gamma_{\tiny{QFT}}\in SU(2^n)\) implementing the DFT on quantum state space, realized in \(O(n^2)\) elementary gates and hence in \(O(n^2)\) minimal time on digital hardware.

QKD

Quantum Key Distribution: a class of quantum communication protocols (e.g.Ekert91 [29] and BBM92 [30]) resting on superposition and entanglement.

QUBO

Quadratic Unconstrained Binary Optimization: the penalized binary reformulation of the MIS problem and several discrete optimization problems.

\(SU(N)\)

Special Unitary group of degree \(N\) (the determinant-one unitary matrices), with Lie algebra \(\mathfrak{su}(N)\) of traceless skew-Hermitian matrices; operator controllability is phrased as reachability of any target \(\Gamma\in SU(N)\) and certified through the Lie-algebraic rank condition on \(\mathfrak{su}(N)\).

UDG(s)

Unit-Disk Graph(s): graphs \(G=(V,E)\) in which two vertices are adjacent precisely when their Euclidean distance is at most the Rydberg-blockade radius \(R_b\); these are the graphs natively realized by neutral-atom registers.

6 The case of steady controls↩︎

Let us consider the case of steady controls. This might give insight even for time evolution controls. Indeed, the action of piece-wise constant controls can be seen as composition of the actions of several steady controls.

7 An example of drift Hamiltonian \(H_0\)↩︎

Inspired from [78], let us give an example of drift Hamiltonian.

First, out of the directed graph \(\mathcal{E}\) defined in subsection 3.1.2, we define the associated undirected graph \[\label{indirect95graph95definition} \mathcal{E}_{\tiny{undirected}}\overset{\scriptscriptstyle\mathrm{def}}{=}\left\{(k,l) \;| \;(k,l)\in \mathcal{E}\right\}\bigcup \left\{(l,k) \;| \;(k,l)\in \mathcal{E}\right\}.\tag{113}\]

The drift Hamiltonian consists of qubit self-energies and static qubit-qubit couplings: \[\label{H950} H_0 = \sum_{k=1}^{127} \frac{\omega_k}{2} Z_k + \sum_{(k,l) \in \mathcal{E}_{\tiny{undirected}}} J_{kl} Z_k Z_l,\tag{114}\] where

• \(\omega_k>0\) is the transition frequency of qubit \(k\);

• \(Z_k\) is the Pauli-\(Z\) operator acting on qubit \(k\);

• \(J_{kl}>0\) is a scalar quantifying the coupling strength between qubits \(k\) and \(l\);

• the addendum \(\sum_{(k,l) \in \mathcal{E}_{\tiny{undirected}}} J_{kl} Z_k Z_l\) models the Ising interaction;

• \(X_k\), \(Y_k\) are Pauli-\(X\) and Pauli-\(Y\) operators acting on qubit \(k\);

• \(\mathcal{E}_{\tiny{undirected}}\subseteq \left\{1,\dots,127\right\}\times \left\{1,\dots,127\right\}\) is the set of coupled qubit pairs; it represents the undirected graph defined in 113 (see figure 2);

(see [39], [79] and [80]).

The Schrödinger equation 12 can be rewritten as \[\label{ibm95brisbane95equation95} i \frac{d}{dt} {\psi(t)} = \Bigg( \sum_{k=1}^{127} \frac{\omega_k}{2} Z_k + \sum_{(k,l) \in \mathcal{E}_{\tiny{undirected}}} J_{kl} Z_k Z_l + \sum_{k=1}^{127} \left( u_k^X(t) X_k + u_k^Y(t) Y_k \right) + \sum_{(c,t) \in \mathcal{E}} v_{ct}(t) Z_c \otimes X_t \Bigg) {\psi(t)}.\tag{115}\]

Note that, by employing this drift Hamiltonian, by slightly modifying the proof of Proposition 3.1, operator controllability holds even without cross-resonance controls. Namely, we can control the system setting \(v_{ct}(t)\equiv 0\). However, cross-resonance controls might be useful to reduce the number of switches.

8 A surrogate problem↩︎

This section introduces a surrogate Optimal Control Problem, which will give a necessary condition for Quantum Advantage (QA).

Let us work in the framework of section 2.

For any time horizon \(T>0\), define the functional \[\label{functionalJ95T95commutator95alongtime} J_T:\mathscr{U}^T\longrightarrow \mathbb{R}\tag{116}\] \[J_T(u)\overset{\scriptscriptstyle\mathrm{def}}{=}\frac{1}{2} \int_0^T\left\|[U(t)\Gamma^*,H_0]\right\|^2dt,\] where

• the state \(U(t)\) solves \[\label{matrix95schrodinger95J95T} \begin{cases} i\frac{d}{dt}U(t) = \big(H_0 + \sum_{j=1}^{m}u_j(t)H_j\big)U(t),& t\in (0,T)\\ U(0)=I,\\ \end{cases}\tag{117}\] with control \(u(t)=(u_k(t))_{k=1}^m\);

• \([\cdot,\cdot]\) denotes the commutator;

• the norm is the matrix norm induced by the \(L^2\) norm¹⁴

Reminding the constraints \(|u(t)|\leq M\) for control in \(\mathscr{U}^T\), by the Direct Methods in the Calculus of Variations (DMCV) [37], there exists a minimizer \(u_T\in \mathscr{U}^T\) for 116 .

For any time horizon \(T>0\) and special unitary operator \(\Gamma\), define the value function \[\label{label95value95function} V(T,\Gamma)\overset{\scriptscriptstyle\mathrm{def}}{=}\inf_{u\in \mathscr{U}^T}J_T=\min_{u\in \mathscr{U}^T}J_T.\tag{118}\]

In the next proposition, we present a necessary condition for QA in terms of estimates of the value function 118 .

The necessary condition ?? can be seen as a specific stabilization-turnpike property on the commutator. A huge literature is available on stabilization of control systems and the turnpike phenomenon; see, for instance, the following articles and books and the references therein [68]–[73], [78], [81]–[83].

8.1 Application to the two representative problems↩︎

The surrogate bound ?? is a necessary condition for Quantum Advantage in the sense of Definition 2.3. The two representative problems of this manuscript fit the scheme as follows.

• QFT on superconducting hardware. Combining Theorem 3.1 with Proposition 8.1, we obtain the sharp quantitative form \[\label{surrogate95QFT} V(T,\Gamma_{\tiny{QFT}})\leq 2\left\|H_0\right\|^2\tau n^2,\qquad \forall T>0,\tag{123}\] already recorded in Corollary 3.2. Equation 123 is checkable on finite-dimensional models of ibm_brisbane: if one can exhibit a sequence of target unitaries \(\Gamma_n \in SU(2^n)\) along which the value function \(V(T,\Gamma_n)\) grows faster than \(n^2\), then the uniformly-bounded-elementary-gate-time assumption of Definition 3.1 fails for the given hardware.

• MIS on neutral-atom hardware. In the analog setting of chapter 4, full operator controllability on \(SU(2^n)\) is ruled out by Proposition 4.2. Hence, Proposition 8.1 does not apply directly to the state-oriented QA of Definition 4.6. A natural line of research (cf. relaxation (R3) in section 4.5) is to formulate a state-targeted analog of ?? , in which the commutator \([U(t)\Gamma^*,H_0]\) is replaced by the residual energy \(\langle \psi(t)|H_C|\psi(t)\rangle - E_{\min}(H_C)\), and the minimal time \(T_{\tiny{min}}\) by the adiabatic time dictated by the instantaneous spectral gap of the interpolating Hamiltonian \(u(t)H_B+(1-u(t))H_C\).

In both cases, the surrogate functional plays the role of a certificate: a polynomial-in-\(n\) upper bound on the value function is a necessary condition for polynomial-in-\(n\) minimal time, hence for Quantum Advantage.

References↩︎

---

1. Pasqal Quantum Computers [5] are available both in gate-based digital mode (enjoying universal quantum computing property) and analog mode. In these notes, we focus on the analog mode.↩︎

2. See https://quantum.cloud.ibm.com/computers?system=ibm_brisbane for details on the ibm\(\_\)brisbane quantum processor.↩︎

3. hereafter, by the word dimension, we mean dimension over \(\mathbb{C}\)↩︎

4. We denoted by \(\mathcal{M}_{N\times N}(\mathbb{C})\) the space of \(N\times N\) matrices with complex entries.↩︎

5. under constraints \(|u(t)|\leq M\) in the control space 5↩︎

6. All along this manuscript, we take the second (s) as unit of measurement of time.↩︎

7. The time horizon \(T\) has to be sufficiently large for controllability to hold. In the physical implementation of quantum computation, this means the DiVincenzo criterion D5 has to be satisfied [31].↩︎

8. in the sense of the tensor product↩︎

9. This group is indeed isomorphic to \((\mathbb{Z}_4,+)\)↩︎

10. Checking whether there exists a relation between the discrete length \(P\) of the path and the continuous time horizon \(T\) (decoherence time) is an interesting research line.↩︎

11. of dimension, over \(\mathbb{C}\), \(2^n\)↩︎

12. the validity of this assumption depends on the configuration ?? and, in particular, on the magnitude of the radius \(R_b\)↩︎

13. For any fixed \(\delta>0\) (the free parameter of the adiabatic theorem, not to be confused with the detuning \(\delta(t)\)), [59] guarantees \(\varepsilon\)-closeness to the instantaneous ground state once \(T_{\mathrm{anneal}}\ge\Omega\big(\|\dot{\gamma}\|_\infty^{1+\delta}\big/[\varepsilon^{\delta}(\Delta_\gamma^{\min})^{2+\delta}]\big)\); the value \(\delta=0\) is inadmissible there, the hidden constant diverging as \(\delta\downarrow 0\). The choice \(\delta=1\) is the unique one rendering the achievable error linear in \(1/T_{\mathrm{anneal}}\), and yields the gap exponent \(2+\delta=3\) together with the squared driving norm \(\|\dot{\gamma}\|_\infty^{2}\). The same \((\Delta_\gamma^{\min})^{-3}\) is the dominant gap dependence in the explicit estimate of [63], whose leading term scales as \(\|\dot{\gamma}\|_\infty^{2}/(\Delta_\gamma^{\min})^{3}\) (with subleading curvature terms \(\propto 1/(\Delta_\gamma^{\min})^{2}\)). For the bell-shaped, fixed-endpoint schedule used here, \(\|\dot{\gamma}\|_\infty\) and \(\|\ddot\gamma\|_\infty\) are \(n\)-independent constants, all absorbed into \(C_{\mathrm{ad}}\).↩︎

14. Let \(A\) be a \(N\times N\) matrix with complex entries. The \(L^2\)-induced matrix norm is \[\left\|A\right\|=\sup_{\mathbf{z}\in \mathcal{H}\setminus \left\{\mathbf{0}_{\mathcal{H}}\right\}}\frac{\left\|A\mathbf{z}\right\|}{\left\|\mathbf{z}\right\|}.\]↩︎