Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000.
10.1109/TQE.2020.DOI

Corresponding author: Tatsuhiko Shirai (email:
tatsuhiko.shirai@aoni.waseda.jp).

# Post-processing variational quantum algorithm for constrained combinatorial
optimization problems

TATSUHIKO SHIRAI1  AND NOZOMU TOGAWA1  Department of Computer Science and
Communications Engineering, Waseda University

###### Abstract

We propose post-processing variational quantum algorithm (pVQA) for solving
constrained combinatorial optimization problems (COPs). COPs are typically
transformed into ground-state search problems of the Ising model on a quantum
annealer or gate-type quantum device. Variational quantum algorithms are used
to find an annealing path that leads to the grand state in a short amount of
time. Post-processing techniques convert the output solutions of the quantum
devices to satisfy the constraints of the COPs. pVQA combines the variational
quantum algorithm and the post-processing technique. We apply it to two
constrained NP-hard COPs: the graph partitioning problem and the quadratic
knapsack problem. pVQA on a simulator shows that a small number of variational
parameters is sufficient to achieve an optimal performance within a
predetermined operation time. Then building upon the simulator results, we
implement pVQA on a quantum annealer and a gate-type quantum device. pVQA
exhibits a superior performance compared with conventional quantum algorithms.

###### Index Terms:

combinatorial optimization problem, Ising model, metaheuristics, quantum
annealing, quantum device, variational quantum algorithm.

=-15pt

##  I Introduction

Quantum annealing is a promising technology widely applied in operator
research, quantum chemistry, and condensed matter physics to determine the
ground state of a given Hamiltonian [1, 2]. For example, adiabatic quantum
annealing obtains the ground state by following an adiabatic path. The
computational time is determined by the global minimum of the spectral gap in
the annealing path [3]. Because the computational time is approximately
proportional to the square of the inverse of the spectral gap and generally
increases with problem size, adiabatic quantum annealing requires a
significant amount of time for large-scale problems.

Recent advances in quantum technology have realized quantum devices [4, 5].
Such devices provide diverse platforms for executing quantum annealing
algorithms, but they are susceptible to various forms of noise, including
thermal and Hamiltonian noises. Noise limits their applicability to quantum
algorithms with low computational costs. For example, an experiment on a
quantum annealer with $2,000$ spins revealed noise effects within a short
timescale of approximately $100\mathrm{ns}$ [6]. Additionally, the
computational accuracy of gate-type quantum devices decreases as the number of
spins increases [7]. Given the finite coherence times of near-term quantum
devices, the development of a quantum annealing algorithm that operates within
a short computation time is crucial.

Figure 1:  Illustration of pVQA for a two-spin COP with a constraint
$\sigma_{1}+\sigma_{2}=0$. Iterating the quantum annealing and classical
optimization $m$ times gives annealing path $s^{(m)}(t)$. $p^{\prime}(\sigma)$
is the probability distribution of the spin configurations obtained by quantum
annealing. When a post-processing is performed, $p(\sigma)$ becomes populated
only with feasible solutions. The classical optimizer calculates the energy
expectation value of the cost function $C(\sigma)$ using $p(\sigma)$ and
updates $s^{(m)}(t)$ (dashed line) to $s^{(m+1)}(t)$ (solid line).

Several ideas have been proposed to overcome the limitation for adiabatic
quantum annealing. One is to search for the optimized annealing path to drive
the system towards the ground state within a short amount of time. Energy-
spectrum information is useful to find such an annealing path. The optimized
annealing path achieves the Grover-type speed up for unstructured search
problems [8] and the significant speed up for problems with a small energy gap
by utilizing diabatic transitions [9, 10]. Variational methods have been
developed as an alternative approach to find the optimized annealing path when
energy-spectrum information is unavailable. Examples include variationally
scheduled quantum simulation for quantum annealers [11] and quantum
approximate optimization algorithm (QAOA) for gate-type quantum devices [12].
Variational methods can discover rapid nonadiabatic annealing paths [13, 14,
15, 16].

Another idea is to employ post-processing techniques. When solving constrained
combinatorial optimization problems (COPs) via quantum annealing, post-
processing enhances the performance. The spin configurations for a constrained
COP are divided into two solutions: feasible and infeasible solutions [17,
18]. Feasible solutions are those that satisfy the constraints. Post-
processing refers to a transformation of infeasible solutions into feasible
ones. Post-processing techniques have been applied to slot-placement problems
and quadratic assignment problems [19, 20].

This study combines a variational method and a post-processing technique to
efficiently solve constrained COPs. Fig. 1 provides a flowchart of our
proposed algorithm, which we call the post-processing variational quantum
algorithm (pVQA). As an illustration, consider a COP with two spins
$\sigma=(\sigma_{1},\sigma_{2})\in\\{-1,1\\}^{\otimes 2}$ subject to a linear
equality constraint $\sigma_{1}+\sigma_{2}=0$. The spin configurations
$(\sigma_{1},\sigma_{2})=(1,-1)$ and $(-1,1)$ are feasible solutions, and all
others are infeasible solutions. First, the quantum device generates a
variational quantum state using the quantum annealing algorithm. Then quantum
measurements of the quantum state provide the probability distribution of the
spin configuration denoted by $p^{\prime}(\sigma)$. The probability
distribution generally has a population over the infeasible solutions (i.e.,
$(\sigma_{1},\sigma_{2})=(-1,-1)$ and $(1,1)$). Post-processing transforms the
infeasible solutions into feasible ones. Hence, the probability distribution
$p(\sigma)$ is populated only with feasible solutions. The classical optimizer
calculates the energy expectation value of the cost function using $p(\sigma)$
and updates the annealing path. Repeating this process finds an optimized
annealing path that gives the high-fidelity ground state.

The three main contributions of this paper are given as follows:

  * •

We propose pVQA as a method for efficiently solving constrained COPs and apply
it to the graph partitioning problem (GPP) and the quadratic knapsack problem
(QKP).

  * •

We execute pVQA on a simulator. pVQA requires a small number of variational
parameters to achieve the optimal performance within a predetermined annealing
time.

  * •

pVQA outperforms conventional algorithms such as quantum annealing and QAOA on
a quantum annealer and a gate-type quantum device.

The rest of this paper is organized as follows. Section II provides the
settings and preliminaries. Section III proposes pVQA. Section IV provides the
simulator results. Section V shows the experimental results on a quantum
annealer and a gate-type quantum device. Section VI discusses the results.
Section VII summarizes this paper.

##  II Preliminaries

Ising models generically map various computationally hard COPs [17, 21, 22].
Ising models are defined on undirected graph $G=(V,E)$ as

$\hat{H}_{\mathrm{Ising}}=\sum_{(i,j)\in
E}J_{ij}\hat{\sigma}_{i}^{z}\hat{\sigma}_{j}^{z}+\sum_{i\in
V}h_{i}\hat{\sigma}_{i}^{z}+H_{0},$ (1)

where $\hat{\sigma}_{i}^{x,y,z}$ are the Pauli spins acting on site $i$,
$J_{ij}\in\mathbb{R}$ denotes an interaction between spin $i$ and spin $j$,
$h_{i}\in\mathbb{R}$ denotes a magnetic field on spin $i$, and
$H_{0}\in\mathbb{R}$. The Ising model for a constrained COP is given as

$\hat{H}_{\mathrm{Ising}}=\hat{H}_{\mathrm{obj}}+\hat{H}_{\mathrm{cst}},$ (2)

where $\hat{H}_{\mathrm{obj}}$ and $\hat{H}_{\mathrm{cst}}$ are Ising models
for the objective function and the constraints of the COP, respectively. Here,
the cost function $C(\sigma)$ is given as

$C(\sigma)=\bra{\sigma}\hat{H}_{\mathrm{obj}}\ket{\sigma}.$ (3)

Here,
$\ket{\sigma}=\ket{\sigma_{1}}\otimes\ket{\sigma_{2}}\otimes\cdots\otimes\ket{\sigma_{|V|}}$,
where $\ket{\sigma_{i}}$ for $i\in V$ is the eigenbasis of
$\hat{\sigma}_{i}^{z}$. Namely,
$\hat{\sigma}_{i}^{z}\ket{\sigma_{i}}=\sigma_{i}\ket{\sigma_{i}}$ for
$\sigma_{i}\in\\{-1,1\\}$.

QUBO (Quadratic Unconstrained Binary Optimization) is equivalent to the Ising
model [23] and is defined on an undirected graph $G_{q}=(V_{q},E_{q})$ as

$Q=\sum_{(i,j)\in E_{q}}q_{ij}x_{i}x_{j}+\sum_{i\in V_{q}}q_{ii}x_{i}+Q_{0},$
(4)

where $x_{i}\in\\{0,1\\}$, $q_{ij}\in\mathbb{R}$, and $Q_{0}\in\mathbb{R}$.
Replacing $x_{i}$ in the QUBO by $(\hat{\sigma}_{i}^{z}+1)/2$ gives the Ising
model.

Quantum annealing searches the ground state of the Ising model using quantum
fluctuations. The quantum state $\ket{\psi(t)}$ obeys the Schrödinger
equation, which is given as

$\frac{d}{dt}\ket{\psi(t)}=-i\left[s(t)\hat{H}_{\mathrm{Ising}}+(1-s(t))\hat{H}_{\mathrm{q}}\right]\ket{\psi(t)},$
(5)

where the Planck constant $\hbar=1$. The annealing path is characterized by
$s(t)$, which is constrained to a value between $0$ and $1$ due to the
hardware constraint of quantum annealers. The source of quantum fluctuations
is the transverse-field Hamiltonian $\hat{H}_{\mathrm{q}}=-\sum_{i\in
V}\hat{\sigma}_{i}^{x}$. The initial state $\ket{\psi(0)}$ is set to the
ground state of $\hat{H}_{\mathrm{q}}$. The annealing time is denoted by $T$.
The output state $\ket{\psi(T)}$ is obtained by solving (5) from $t=0$ to
$t=T$.

##  III pVQA

This section details pVQA. First, pVQA is formulated. Then we give three types
of the annealing schedule since the appropriate annealing schedule depends on
the type of quantum devices. Finally, we demonstrate the applicability of pVQA
for COPs with a typical constraint.

###  III-A Formulation of pVQA

Fig. 1 illustrates the pVQA algorithm. The algorithm calculates the Ising
model corresponding to a COP and the initial annealing path $s^{(0)}(t)$ for
$t\in[0,T]$ as the input. Then iterating the following process $m$ times gives
the annealing path $s^{(m)}(t)$.

The quantum device performs the quantum annealing algorithm along the
annealing path $s^{(m)}(t)$ to generate $\ket{\psi(T)}$. The probability
distribution of the spin configuration is given as

$p^{\prime}(\sigma)=\left|\langle\sigma\ket{\psi(T)}\right|^{2}.$ (6)

When using a real quantum device, the probability distribution is
approximately obtained by repeating the quantum projection measurements of
$\ket{\psi(T)}$ on the computational basis.

Then post-processing is performed. The post-processing is defined by mapping
$P$: $P\sigma\rightarrow\sigma$, which transforms infeasible solutions into
feasible ones. The probability distribution is recalculated as

$p(\sigma)=\sum_{\sigma^{\prime}|\sigma=P\sigma^{\prime}}p^{\prime}(\sigma^{\prime}),$
(7)

which is populated only with feasible solutions. Here, poor-quality solutions
can be discarded to achieve a high-quality probability distribution. The
energy expectation value of the cost function is given as

$E=\sum_{\sigma}p(\sigma)C(\sigma).$ (8)

A classical optimizer modifies the annealing path $s^{(m)}(t)$ to lower the
energy expectation value and updates $s^{(m)}(t)$ to $s^{(m+1)}(t)$. It relies
on an optimization algorithm such as the gradient descent method or the Powell
method to construct a progressively optimized sequence of variational
parameters [24].

Finally, when the annealing path is optimized, the performance of pVQA is
evaluated using the probability distribution $p(\sigma)$.

As a comparison to pVQA, a variational quantum algorithm without post-
processing is introduced. We call the algorithm variational quantum algorithm
(VQA). The quantum device performs the quantum annealing algorithm. A
classical computer calculates the energy $E^{\prime}$ as

$E^{\prime}=\sum_{\sigma}p^{\prime}(\sigma)C^{\prime}(\sigma),$ (9)

where the cost function $C^{\prime}(\sigma)$ is given as

$C^{\prime}(\sigma)=\bra{\sigma}\hat{H}_{\mathrm{Ising}}\ket{\sigma}.$ (10)

Since constraint Hamiltonian $H_{\mathrm{cst}}$ of the cost function increases
the energy of infeasible solutions, feasible solutions are easily obtained. A
classical optimizer lowers $E^{\prime}$ to update the annealing path
$s^{(m)}(t)$.

###  III-B Annealing schedules

We consider three types of annealing schedules: continuous, linear, and QAOA
schedules. The continuous schedule represents $s(t)$ as a continuous function,
the linear schedule represents $s(t)$ as a linear function, and the QAOA
schedule has $s(t)$ that takes values of either zero or one. Although the
continuous schedule shows the best performance among the three, its
implementation on quantum devices remains challenging. On the other hand, the
linear schedule can be performed on quantum annealers, whereas the QAOA
schedule is easily implemented on gate-type quantum devices.

Figure 2:  (a)–(c): Optimal annealing paths in the continuous schedule for
different annealing times of $T=0.1,1$, and $10$, respectively. Each line
corresponds to the optimal annealing path for a different GPP. (d): Success
probability as a function of annealing time. Points in Fig.(a)–(c) are marked.

Figure 3:  (a) Example of the linear schedule. Variational parameters are
given by $s_{1}$ and $s_{2}$. (b) Example of the QAOA schedule with $2$ layers
($p=2$). Variational parameters are given by $\\{s_{i}\\}_{i=1}^{4}$

First, we discuss the optimal annealing path $s^{*}(t)$ in the continuous
schedule. According to optimal control theory, for a short annealing time $T$,
$s^{*}(0)=1$ and $s^{*}(T)=0$, and the annealing between the two can be a
smooth path [25]. The results can be extended straightforwardly to pVQA with
post-processing.

Fig. 2 (a)–(c) shows the three types of optimal annealing paths for $10$ GPPs
with $8$ nodes, which depend on the annealing time. Fig. 2 (d) plots the
success probability as a function of the annealing time. Here, the success
probability denotes the probability of obtaining the optimum solution of a GPP
when quantum annealing is computed along the optimal annealing path and a
subsequent post-processing is performed (see Sec. III-C for details). The
success probability increases with annealing time. Short annealing times
produce a bang-bang-type annealing path. Annealing starts with the Ising
Hamiltonian and quickly transitions to the transverse-field Hamiltonian. The
transition occurs at the midpoint of the annealing time. Intermediate
annealing times result in a bang-anneal-bang-type annealing path. Annealing
begins with the Ising Hamiltonian, which follows a continuous function that
ends with the transverse-field Hamiltonian. Long annealing times generate
annealing paths that closely resemble the standard ones, which start with the
transverse-field Hamiltonian and end with the Ising Hamiltonian. Below, we
call short, intermediate, and long annealing time regimes the bang-bang, bang-
anneal-bang, and anneal regimes, respectively. Reference [25] reported similar
observation.

The linear schedule has two variational parameters $s_{1}$ and $s_{2}$, which
represent the initial and final values of $s(t)$, respectively (see Fig. 3
(a)). The annealing path is given as

$s(t)=s_{1}+\frac{s_{2}-s_{1}}{T}t.$ (11)

It should be noted that previous studies fixed $s(0)=0$ and $s(T)=1$, and then
used the values of $s(t)$ during annealing as variational parameters [11, 15,
16]. Unlike previous studies, we adopt $s_{1}$ and $s_{2}$ as variational
parameters since the optimal annealing path in the continuous schedule does
not always start with $s(0)=0$ or end with $s(T)=1$ (see Fig. 2). The linear
schedule is approximately implemented on a quantum annealer (see Sec. V-B1 for
details).

The QAOA schedule has $p$ layers. Each layer consists of two variational
parameters (see Fig. 3 (b)). Thus, there are $2p$ variational parameters
denoted by $\\{s_{i}\\}_{i=1}^{2p}$. The time duration of $s(t)=1$ and
$s(t)=0$ for layer $\ell\in\\{1,\ldots,p\\}$ is respectively determined by

$s(t)=\left\\{\begin{aligned} &1\quad\text{ for }\quad s_{2\ell-2}\leq
t<s_{2\ell-1}\\\ &0\quad\text{ for }\quad s_{2\ell-1}\leq
t<s_{2\ell},\end{aligned}\right.$ (12)

where $s_{0}=0$. We impose the following conditions on the variational
parameters: $s_{i-1}\leq s_{i}$ for $i\in\\{1,\ldots,2p\\}$ and $s_{2p}\leq
T$. The quantum state is not time-evolved between $t\in[s_{2p},T]$. These
conditions allow the performance of the QAOA schedule to be compared with the
other types of schedules. The QAOA schedule is easily implemented on a real
gate-type quantum device (see Sec. V-B2 for details).

###  III-C Applicability of pVQA

pVQA is applicable when post-processing transforms all infeasible solutions
into feasible ones. Here, we demonstrate the presence of such post-processing
for combinatorial optimization problems with a typical constraint such as the
$k$-hot constraint or the inequality constraint. The $k$-hot constraint
appears in GPPs and graph-coloring problems, whereas the inequality constraint
appears in knapsack problems and set covering problems [17]. It should be
noted that post-processing is not found for all types of the constraints. This
situation occurs when finding a feasible solution is NP-complete. Extending
the applicability of pVQA to COPs with a combination of $k$-hot constraints
and inequality constraints remains a challenge.

First, we consider a COP with an inequality constraint:

######  Problem 1.

For binary variables $x_{i}\in\\{0,1\\}$ for $i\in V$, find a configuration
that minimizes QUBO for the objective function $Q_{\mathrm{obj}}$ under the
following constraint

$b_{\mathrm{min}}\leq\sum_{i\in V}a_{i}x_{i}\leq b_{\mathrm{max}}$ (13)

where $b_{\mathrm{min}}$, $b_{\mathrm{max}}$, and $a_{i}$ for $i\in V$ are
integers.

Then we prove the following theorem.

######  Theorem 1.

Consider the Hamiltonian $Q^{\prime}$ for problem 1, which is given as

$Q^{\prime}=Q_{\mathrm{obj}}+A^{\prime}Q^{\prime}_{\mathrm{cst}}$ (14)

where $A^{\prime}>0$ denotes a constraint coefficient and

$Q^{\prime}_{\mathrm{cst}}=\max\left\\{0,-b_{\mathrm{max}}+\sum_{i\in
V}a_{i}x_{i},b_{\mathrm{min}}-\sum_{i\in V}a_{i}x_{i}\right\\}.$ (15)

Then all local minimum solutions of $Q^{\prime}$ are feasible solutions under
the following conditions:

  1. 1.

$A^{\prime}>\Delta Q_{\mathrm{obj}}$ where $\Delta Q_{\mathrm{obj}}$ is the
maximum energy change of $Q_{\mathrm{obj}}$ when flipping a binary variable.

  2. 2.

$b_{\mathrm{max}}-b_{\mathrm{min}}\geq\max_{i\in V}|a_{i}|-1$.

  3. 3.

Feasible solutions exist.

Here, a flip indicates a change in the value of a binary variable from $0$ to
$1$ or vice versa. Then the local minimum solution is defined as a solution
that does not lower the energy of $Q^{\prime}$ by flipping any binary
variable.

###### Proof of Theorem 1.

To prove the theorem, we show that all infeasible solutions are not local
minimum solutions under the three conditions. Suppose that $\\{x_{i}\\}_{i\in
V}$ is an infeasible solution. Then

$b_{\min}\geq\sum_{i\in V}a_{i}x_{i}+1$ (16)

or

$b_{\max}\leq\sum_{i\in V}a_{i}x_{i}-1$ (17)

is satisfied. When (16) holds, we find from the second condition that

$\left(\sum_{i\in V}a_{i}x_{i}\right)+|a_{j}|\leq
b_{\mathrm{min}}+|a_{j}|-1\leq b_{\mathrm{max}}.$ (18)

This indicates that the configurations obtained by flipping a single binary
variable do not satisfy (17).

Next, we show that the infeasible solution is not a local minimum solution
using a proof by contradiction. Assume that the infeasible solution is a local
minimum solution. Equation (18) implies that if a flip increases the value of
$\sum_{i\in V}a_{i}x_{i}$, it lowers the value of $Q^{\prime}$ when
$A^{\prime}>\Delta Q_{\mathrm{obj}}$. Therefore, a flip should not increase
the value of $\sum_{i\in V}a_{i}x_{i}$, implying that $a_{i}\geq 0$ when
$x_{i}=1$ and $a_{i}\leq 0$ when $x_{i}=0$. Thus,

$b_{\mathrm{min}}>\sum_{i|a_{i}\geq 0}a_{i}\geq\sum_{i\in
V}a_{i}x^{\prime}_{i}$ (19)

for any configuration $\\{x^{\prime}_{i}\\}$. This contradicts the third
condition that feasible solutions exist and indicates that $\\{x_{i}\\}$ is
not a local minimum solution. For infeasible solutions that satisfy (17),
similar arguments show that they are not local minimum solutions.
Consequently, when the three conditions are satisfied, all local minimum
solutions are feasible solutions. ∎

Here, we comment on the setting of $A^{\prime}$. When $Q_{\mathrm{obj}}$ is
formulated as QUBO (i.e., $Q_{\mathrm{obj}}=\sum_{(i,j)\in
E_{q}}q_{ij}x_{i}x_{j}+\sum_{i\in V_{q}}q_{i}x_{i}$), an upper bound of
$\Delta Q_{\mathrm{obj}}$ is given as

$\Delta Q_{\mathrm{obj}}\leq\max_{i\in V_{q}}\Big{(}|q_{ii}|+\sum_{j|(i,j)\in
E_{q}}|q_{ij}|\Big{)}.$ (20)

$A^{\prime}$ can be set to a value larger than the right-hand side of the
equation.

Next, we consider a COP with a $k$-hot constraint:

######  Problem 2.

For binary variables $x_{i}\in\\{0,1\\}$ for $i\in V$, find a configuration
that minimizes QUBO for the objective function $Q_{\mathrm{obj}}$ under the
constraint

$\sum_{i\in V^{\prime}}x_{i}=k$ (21)

where $k$ is an integer and $V^{\prime}\subseteq V$.

Problem 1 with $b_{\mathrm{min}}=b_{\mathrm{max}}=k$, $a_{i}=1$ for $i\in
V^{\prime}$, and $a_{i}=0$ for $i\in V\setminus V^{\prime}$ is reduced to
Problem 2. Thus, Theorem 1 gives the following corollary.

######  Corollary 2.

Consider Hamiltonian $Q^{\prime}$ for problem 2 as

$Q^{\prime}=Q_{\mathrm{obj}}+A^{\prime}\left|\sum_{i\in
V^{\prime}}x_{i}-k\right|.$ (22)

Then all local minimum solutions of $Q^{\prime}$ are feasible solutions under
the conditions that $A^{\prime}>\Delta Q_{\mathrm{obj}}$ and
$k\leq|V^{\prime}|$.

Post-processing is given by a local optimization method using the property
that all local minimum solutions are feasible solutions. The local
optimization method flips a binary variable to lower energy $Q^{\prime}$.
Since an infeasible solution is not a local minimum solution, repeating the
local optimization method can give a feasible solution. In this study, we
adopt the greedy method as the local optimization method. The greedy method
flips a binary variable resulting in the lowest energy of $Q^{\prime}$ when it
is flipped. We perform the greedy method for all configurations obtained via
the quantum annealing algorithm. Namely, if the obtained feasible solution is
not a local minimum solution, post-processing transforms it into a feasible
solution with a lower energy.

####  III-C1 Examples of constrained COPs: GPP and QKP

We consider two types of constrained COPs: GPP and QKP. Both problems are
categorized as NP-hard [26, 27].

GPP divides the node set of a given graph $G_{g}=(V_{g},E_{g})$ into two
subsets with equal size, minimizing the number of cuts. Here, it is assumed
that the graph has an even number of nodes. The cut denotes the edge
connecting the two subsets. The binary variable $x_{i}\in\\{0,1\\}$ is
assigned for each node such that $x_{i}=0$ ($x_{i}=1$) indicates that node $i$
belongs to the one (the other) subset. Then this problem has a $|V_{g}|/2$-hot
constraint, which is given as

$\sum_{i\in V_{g}}x_{i}=\frac{|V_{g}|}{2}.$ (23)

pVQA is applicable to the problem since the constraint satisfies the
conditions of Corollary 2. QUBO for the GPP is given as [28]

$\displaystyle Q_{\mathrm{gpp}}=Q_{\mathrm{obj}}+Q_{\mathrm{cst}},$ (24)
$\displaystyle\left\\{\begin{aligned} Q_{\mathrm{obj}}&=-2\sum_{(i,j)\in
E_{g}}x_{i}x_{j}+\sum_{i\in V_{g}}k_{i}x_{i},\\\
Q_{\mathrm{cst}}&=A\left(\sum_{i\in
V_{g}}x_{i}-\frac{|V_{g}|}{2}\right)^{2},\end{aligned}\right.$

where $k_{i}$ denotes the degree of node $i$. Here, $Q_{\mathrm{obj}}$ and
$Q_{\mathrm{cst}}$ are QUBOs for the objective function and the constraints,
respectively. $A\in\mathbb{R}$ is the constraint coefficient.

QKP finds a set of items to yield the highest profit within the capacity of
the knapsack. The set of $n$ items with weights $\\{w_{i}\\}_{i=1}^{n}$ and
profits $\\{p_{ij}\\}_{i\leq j}^{n}$, and the capacity of the knapsack $C$ are
given. Here, $p_{ii}$ denotes the profit of item $i$ and $p_{ij}$ denotes the
additional profit when item $i$ and item $j$ are chosen. The binary variable
$x_{i}\in\\{0,1\\}$ is assigned for each item such that $x_{i}=1$ when item
$i$ is chosen and $x_{i}=0$ when item $i$ is not chosen. This problem has an
inequality constraint, which is given as

$\sum_{i=1}^{n}w_{i}x_{i}\leq C.$ (25)

pVQA is applicable since the constraint satisfies the conditions of Theorem 1.
QUBO for the QKP is given as

$\displaystyle Q_{\mathrm{qkp}}=Q_{\mathrm{obj}}+Q_{\mathrm{cst}},$ (26)
$\displaystyle\left\\{\begin{aligned}
Q_{\mathrm{obj}}&=-\sum_{i=1}^{n}\sum_{j=i}^{n}p_{ij}x_{i}x_{j},\\\
Q_{\mathrm{cst}}&=A\left(\sum_{i=1}^{n}\frac{w_{i}x_{i}}{C}\right)^{2},\end{aligned}\right.$

where $Q_{\mathrm{obj}}$ and $Q_{\mathrm{cst}}$ are QUBOs for the objective
function and the constraints, respectively. $A$ is the constraint coefficient.
Here, we adopt mapping in [29] for an inequality constraint. Unlike other
mappings [30], it does not require additional auxiliary binary variables and
is suitable for near-term quantum devices with severe limitations on the input
number of spins.

##  IV Simulator results

The performance of pVQA is initially evaluated using a simulator. The
simulator employs the fourth-order RungeKutta method to solve the Schrödinger
equation in (5). We use Python 3.7.6 integrated with intel Fortran as the
implementation language.

###  IV-A Instances of COPs

We generate $10$ instances for GPPs and $10$ instances for QKPs for each
problem size. The GPP instances are specified by the undirected graph
$G_{g}=(V_{g},E_{g})$. Random graphs with an edge density of $0.5$ are
generated. The QKP instances with $n$ items are generated by benchmarking
instances with the $100$ items listed in [31]. They are labeled
$100\\_100\\_i$ where $i\in\\{1,\ldots,10\\}$ denotes the instance. Each
instance is specified by a profit matrix $\\{p^{(i)}_{jk}\\}_{j\leq k}^{100}$,
weight $\\{w^{(i)}_{j}\\}_{j=1}^{100}$, and knapsack capacity $C^{(i)}$. To
generate QKPs with $n$ items, we use a profit matrix
$\\{p^{(i)}_{jk}\\}_{j\leq k}^{n}$, weight $\\{w^{(i)}_{j}\\}_{j=1}^{n}$, and
knapsack capacity $\lfloor nC^{(i)}/100\rfloor$. Here, $\lfloor
x\rfloor\coloneqq\max\\{m\in\mathbb{Z}|m\leq x\\}$ is the usual floor
function. The optimum solution for each problem is obtained by a state-of-the-
art heuristic Ising-model classical solver [32].

For each problem instance, we calculate the Ising model using the QUBOs in
(24) and (26). The coefficients of the Ising model are rescaled so that the
maximal absolute value of $\\{J_{ij}\\}_{(i,j)\in E}$ and $\\{h_{i}\\}_{i\in
V}$ is one. This rescaling determines the timescale for quantum annealing.

###  IV-B Method

We compare the performances of pVQA, VQA, pQA, and QA. Here, pQA represents
quantum annealing with post-processing, and QA represents quantum annealing
without post-processing. In pQA and QA, we adopt a linearly interpolated
annealing path from $s(0)=0$ to $s(T)=1$. pVQA and VQA optimize the annealing
path using a classical optimizer. For continuous schedules, we follow the
method in [25] based on optimal control theory and use a gradient descent
method as a classical optimizer with an initial condition of $s(t)=0.5$ for
$t\in[0,T]$. For linear and QAOA schedules, we adopt the Powell method
implemented in SciPy as a classical optimizer [33]. For the linear schedule,
the maximum number of iterations is set to $10$ with initial values of
$s_{1}=s_{2}=0.5$. For the QAOA schedule, the maximum number of iterations is
set to $10p$ and initially $s_{i}=0$ for $i\in\\{1,\ldots,2p\\}$ [34]. The
default values are used for the remaining input parameters.

The constraint coefficients $A$ are determined using the procedure in [30].
Hereafter, $p(\sigma)$ and $p^{\prime}(\sigma)$ respectively denote the
probability distributions in (7) and (6) obtained for either the optimized
annealing path in pVQA and VQA or the given annealing path in pQA and QA. We
calculate the feasible solution rate and the average cost function. The
feasible solution rate is $1$ for pVQA and pQA due to the post-processing. The
feasible solution rate for VQA and QA is calculated as

$p_{\mathrm{FS}}=\sum_{\sigma\in F}p^{\prime}(\sigma),$ (27)

where $F$ is the feasible solution subspace. The average cost function is
given as

$C_{\mathrm{ave}}=\left\\{\begin{aligned}
&\sum_{\sigma}C(\sigma)p(\sigma)\text{ for pVQA and pQA},\\\
&\frac{\sum_{\sigma\in F}C(\sigma)p^{\prime}(\sigma)}{p_{\mathrm{FS}}}\text{
for VQA and QA}.\end{aligned}\right.$ (28)

$C_{\mathrm{ave}}$ is calculated for the feasible solutions for VQA and QA. A
smaller value of the average cost function indicates a higher performance. To
systematically determine the optimum value of the constraint coefficient, we
set the threshold value of the feasible solution rate to $0.1$. We repeatedly
solve each problem instance while varying the constraint coefficient. Then we
determine the parameter regime that yields a feasible solution rate above the
threshold value. Finally, we search for the optimal value of $A$ to minimize
the average cost function. The precision threshold of the constraint
coefficient is set to $1$ for GPPs and $200$ for QKPs.

The performances of pVQA, VQA, pQA, and QA are compared using the success
probability averaged over the $10$ problem instances for each problem size.
The success probability $p_{\mathrm{suc}}$ is given as

$p_{\mathrm{suc}}=\left\\{\begin{aligned} &\sum_{\sigma\in S}p(\sigma)\text{
for pVQA and pQA},\\\ &\sum_{\sigma\in S}p^{\prime}(\sigma)\text{ for VQA and
QA},\end{aligned}\right.$ (29)

where $S$ is the set of optimum solutions.

###  IV-C Results

Figure 4:  Results for GPPs. Annealing time dependence of the success
probability of $8$ node GPPs for (a) the linear schedule and (b) the QAOA
schedule. Continuous schedule is depicted by pentagons (black) for comparison.
(c): Dependence of the success probability on the number of nodes for pVQA,
VQA, pQA, and QA. In pVQA and VQA, data for the linear schedule and the QAOA
schedule are represented by the filled and open symbols, respectively.

Figure 5:  Results for QKPs. Success probability of $8$ item QKPs as a
function of annealing time for (a) the linear schedule and (b) QAOA schedule.
Continuous schedule is depicted by pentagons (black) for comparison. (c):
Dependence of the success probability on the number of items for pVQA, VQA,
pQA, and QA. In pVQA and VQA, data for the linear schedule and QAOA schedule
are represented by filled and open symbols, respectively.

Fig. 4 shows the results for the GPPs. The success probability for the linear
schedule increases with the annealing time. The linear schedule almost
reproduces the success probability of the continuous schedule for all
annealing times (Fig. 4 (a)). For the QAOA schedule, $p=1$ is sufficient for
the bang-bang regime ($T\sim 10^{-1}$), whereas $p=3$ is appropriate for the
bang-anneal-bang regime ($T\sim 1$) to achieve the success probability of the
continuous schedule (Fig. 4 (b)). However, the performance of the QAOA
schedule degrades in the anneal regime ($T\sim 10$) because the time steps in
the QAOA schedule are too large to accurately approximate the continuous
schedule.

Fig. 4 (c) compares the success probability of pVQA with VQA, pQA, and QA when
the annealing time is $T=1$ and the number of layers for the QAOA schedule is
$p=3$. Filled symbols connected by solid lines denote the results for the
linear schedule, whereas open symbols connected by dashed lines indicate the
results for the QAOA schedule. For all the problem sizes, the linear and QAOA
schedules exhibit almost the same performances. pVQA significantly outperforms
the conventional methods of QA and QAOA (i.e., VQA for the QAOA schedule).

The simulator results for the QKPs are qualitatively similar to those for the
GPPs (Fig. 5). The linear schedule approximates the continuous schedule well
for all annealing times (see Fig. (a)). The QAOA schedule with a small value
of $p$ provides a good approximation of the continuous schedule in the bang-
bang regime and the bang-anneal-bang regime, but its performance degrades in
the anneal regime (Fig. 5 (b)). Fig. 5 (c) compares the success probability of
pVQA with the conventional methods. Note that we set $p=3$ for the QAOA
schedule and $T=1$. pVQA outperforms the conventional methods.

Table I shows the optimized values of variational parameters $s_{1}$ and
$s_{2}$ for the linear schedule. GPPs and QKPs display the similar dependences
of $s_{1}$ and $s_{2}$ on the annealing time. For a short annealing time,
$s_{1}\simeq 1$ and $s_{2}\simeq 0$. In contrast, $s_{1}\simeq 0$ and
$s_{2}\simeq 1$ for a long annealing time. As the annealing time increases,
$s_{1}$ gradually decreases, whereas $s_{2}$ gradually increases. These
annealing time dependences of $s_{1}$ and $s_{2}$ are consistent with the
optimal annealing paths in the continuous schedule (see Fig. 2).

TABLE I: Optimized values of variational parameters $s_{1}$ and $s_{2}$ for
the linear schedule. Values in parentheses denote the standard deviation.

| GPP | QKP
---|---|---
$T$ | $s_{1}$ | $s_{2}$ | $s_{1}$ | $s_{2}$
$0.1$ | $1.0(0)$ | $0.0(0)$ | $0.93(5)$ | $0.14(9)$
$0.2$ | $1.0(0)$ | $0.0(0)$ | $0.96(3)$ | $0.16(10)$
$0.5$ | $0.98(1)$ | $0.0(0)$ | $0.99(1)$ | $0.17(11)$
$1$ | $0.50(2)$ | $0.35(3)$ | $0.99(1)$ | $0.16(11)$
$2$ | $0.18(3)$ | $0.67(4)$ | $0.65(5)$ | $0.48(6)$
$5$ | $0.10(2)$ | $0.79(3)$ | $0.65(5)$ | $0.48(6)$
$10$ | $0.05(2)$ | $0.84(4)$ | $0.25(12)$ | $0.92(5)$

##  V Experiments with quantum devices

We conducted experiments of pVQA on a quantum annealer and a gate-type quantum
device. We use a D-Wave annealer as a quantum annealer. The quantum annealing
hardware embeds a maximum of $180$ spins on a complete graph [35]. As a gate-
type quantum device, we use ibmq_quito, ibmq_manila, ibmq_lima, and
ibmq_belem, which are IBM Quantum Canary Processors [36]. The number of spins
available is $5$ or $7$. Both experiments used Python 3.7.6 as the
implementation language.

###  V-A Instances of COPs

Figure 6:  Four-node GPP used in experiments on the gate-type quantum device.
Dashed line denotes the optimum solution.

The quantum annealing experiment generates $10$ problem instances for GPPs and
$7$ problem instances for QKPs. For GPPs, $5$ random graphs with
$|V_{g}|\in\\{32,64\\}$ are generated. The edge density is set to $0.5$. The
problem instances are denoted as GPP_$n$_$i$ where $n=|V_{g}|$ and $i$
represents the label of the random graph. For QKPs, $5$ problems with $50$
items and $2$ problems with $100$ items are generated. We use the benchmarking
instances $100\\_100\\_i$ to generate the problem instances [31]. Problem
instances with $50$ items are generated in the same process as Sec. IV. The
problem instances are named as QKP_$n$_$i$, where $n$ is the number of items
and $i$ is the label of the benchmarking instance. The gate-type quantum
device uses a $4$-node GPP (Fig. 6). The optimal solution for each problem is
obtained by a heuristic Ising-model classical solver [32] or [31].

For each problem instance, we generate the Ising model using the QUBOs in (24)
and (26). For the experiment on the quantum annealer, auto-scaling of the
solver is used to adjust the coefficients of the Ising model. For the
experiments on the gate-type quantum device, the coefficients of the Ising
model are rescaled as shown in Sec. IV.

###  V-B Method

####  V-B1 Implementation on the quantum annealer

We compare the performances of pVQA, pQA, and QA on the quantum annealer.
Here, VQA is excluded due to its poor performance compared to pVQA and pQA
(Sec. IV). We set the annealing time to $5\mathrm{\mu s}$. pVQA adopts the
annealing path close to that of the linear schedule. The annealing path is
controlled by a parameter called anneal fraction $s$, which assumes a value
between $0$ and $1$. The strength of the transverse fields decreases with $s$.
The values of $s$ at initial time $s_{0}$ and at end time $s_{3}$ are fixed to
$0$ and $1$, respectively. We use the values of $s$ at $0.5\mathrm{\mu s}$ and
$4.5\mathrm{\mu s}$ as variational parameters. They are denoted by $s_{1}$ and
$s_{2}$, respectively. The set of parameters $\\{s_{i}\\}_{i=0}^{3}$ produces
a piecewise linear annealing path. Two types of classical optimizers are
adopted to determine $s_{1}$ and $s_{2}$. One uses the Powell method
implemented in SciPy, where the initial values of $s_{1}$ and $s_{2}$ are
$0.5$ and the maximum number of iterations is $10$. The other uses the grid
search method to find the optimal values of $s_{1}$ and $s_{2}$. The precision
thresholds of $s_{1}$ and $s_{2}$ are set to $0.1$. The probability
distribution $p(\sigma)$ in (7) is generated by the top $50$ high-quality
solutions in terms of the cost function (i.e., $C(\sigma)$) out of the $100$
solutions obtained by the quantum measurements. pQA and QA use the default
annealing schedule. Namely, annealing begins with $s=0$ and ends with $s=1$
with a linear interpolation between them.

Then we optimize the constraint coefficient $A$ and the chain strength for
each problem. The chain strength is a parameter for minor embedding [37, 38].
Here, the parameters are determined as follows. We obtain $100$ solutions by
performing quantum annealing along the optimized annealing path for pVQA and
the given annealing path for pQA and QA. We use the top $50$ high-quality
solutions in terms of the cost function (i.e., $C(\sigma)$ for pVQA and pQA
and $C^{\prime}(\sigma)$ for QA) to compute both the feasible solution rate
and the average cost function. The feasible solution rate is given by the
ratio to obtain the feasible solutions in the $50$ solutions. Then a parameter
regime is selected to yield a feasible solution rate above the threshold value
of $0.1$. Afterwards, the optimal values of the constraint coefficient and the
chain strength are searched to minimize the average cost function. The average
cost function is given by the average of $C(\sigma)$ over the feasible
solutions in the $50$ solutions. The precision threshold of the constraint
coefficient $A$ is $1$ for GPPs and $1000$ for QKPs, whereas that of the chain
strength is $10$.

Finally, the performance is measured by the success probability and the
residual energy. Success probability $p_{\mathrm{suc}}$ is the ratio to obtain
the optimal solutions in the $50$ solutions. Residual energy $R_{50}$ is the
difference between the average cost function and the optimum one. A smaller
value of the residual energy indicates a better performance.

In experiments, each algorithm is executed $5$ times for each problem
instance. In Section V-C, we show the average and the standard deviation of
the success probability and the residual energy based on the $5$ samples.

####  V-B2 Implementation on the gate-type quantum device

We compare the performances between pVQA and VQA because pQA and QA are
difficult to execute on the gate-type quantum device. The quantum circuit for
the QAOA schedule with $p$ layers is given as

$\left(\prod_{i=1}^{p}\hat{U}_{\mathrm{q}}(s_{2i}-s_{2i-1})\hat{U}_{\mathrm{Ising}}(s_{2i-1}-s_{2i-2})\right)\ket{\psi(0)}$
(30)

where $\hat{U}_{\mathrm{q}}(s)\coloneqq e^{-i\hat{H}_{\mathrm{q}}s}$,
$\hat{U}_{\mathrm{Ising}}(s)\coloneqq e^{-i\hat{H}_{\mathrm{Ising}}s}$, and
$\ket{\psi(0)}$ is the ground state of $\hat{H}_{\mathrm{q}}$. We use Qiskit
library to build the quantum circuit [39]. Here, we adopt the QAOA schedule
with $T=1$ and $p=1$. We use the Powell method implemented in SciPy as a
classical optimizer with a maximum of $10$ iterations. The initial values of
the variational parameters (i.e., $s_{1}$ and $s_{2}$) are set to zero. The
probability distribution $p(\sigma)$ for pVQA in (7) and $p^{\prime}(\sigma)$
for VQA in (6) are generated by the $100$ solutions obtained by the quantum
measurements.

We then optimize the constraint coefficient $A$ by minimizing the average cost
function. Quantum annealing is repeatedly performed along the optimized
annealing path $100$ times. The average cost function is given by the average
of the cost function (i.e., $C(\sigma)$ for pVQA and $C^{\prime}(\sigma)$ for
VQA) over the $100$ solutions. The precision threshold of the constraint
coefficient $A$ is set to $1$.

Finally, the performance on the gate-type quantum device is measured by the
success probability from $100$ solutions.

In experiments, each algorithm is executed $5$ times. Below, we show the
average and the standard deviation of the success probability based on the $5$
samples.

###  V-C Results

Table II shows the performances of pVQA, pQA, and QA on the quantum annealer.
Post-processing significantly improves the performance. The choice of the
classical optimizer influences the pVQA performance. The grid search method
outperforms the Powell method. pVQA with the grid search method gives better
results than pQA for all the problem instances, but pVQA with the Powell
method shows a similar performance to pQA. pVQA with the grid search method
finds optimal solutions, except for GPPs with $64$ nodes. The optimal values
of $s_{1}$ and $s_{2}$ strongly fluctuate over the problem instances.

Table III shows the performances of pVQA and VQA on the gate-type quantum
device. pVQA outperforms VQA. The success probability of pVQA on the quantum
device is slightly worse than that on the simulator. This difference is
attributed to the inherent noise in the quantum device.

TABLE II: Experimental results of pVQA, pQA, and QA for GPPs and QKPs on the
quantum annealer. Residual energy, success probability, and feasible solution
rate are denoted by $R_{50}$, $p_{\mathrm{suc}}$, and $p_{\mathrm{FS}}$,
respectively. Values in parentheses are the standard deviation. Average
indicates the average of $R_{50}$ and $p_{\mathrm{suc}}$ over the GPPs and
QKPs with the same problem size. Opt denotes the cost function of the optimal
solution.

|  | pVQA (Powell) | pVQA (grid search)
---|---|---|---
instance | Opt | $R_{\mathrm{50}}$ | $p_{\mathrm{suc}}$ | $s_{1}$ | $s_{2}$ | $R_{\mathrm{50}}$ | $p_{\mathrm{suc}}$ | $s_{1}$ | $s_{2}$
GPP_32_1 | $91$ | $0.19(8)$ | $0.82(7)$ | $0.32(9)$ | $0.59(6)$ | $0.02(2)$ | $0.98(2)$ | $0.3$ | $0.7$
GPP_32_2 | $92$ | $2.62(29)$ | $0.11(2)$ | $0.38(13)$ | $0.65(8)$ | $2.12(9)$ | $0.13(2)$ | $0.0$ | $0.6$
GPP_32_3 | $93$ | $4.58(25)$ | $0.01(1)$ | $0.37(10)$ | $0.63(8)$ | $4.14(1)$ | $0.01(1)$ | $0$ | $0.5$
GPP_32_4 | $89$ | $2.32(38)$ | $0.14(2)$ | $0.40(9)$ | $0.59(5)$ | $1.68(11)$ | $0.22(2)$ | $0.2$ | $0.5$
GPP_32_5 | $104$ | $2.18(48)$ | $0.18(4)$ | $0.59(8)$ | $0.57(8)$ | $1.66(15)$ | $0.30(2)$ | $0.2$ | $1.0$
Average | $-$ | $2.38$ | $0.25$ | $-$ | $-$ | $1.92$ | $0.33$ | $-$ | $-$
GPP_64_1 | $428$ | $6.44(41)$ | $0.0(0)$ | $0.63(12)$ | $0.44(8)$ | $5.80(10)$ | $0.0(0)$ | $0.9$ | $0.3$
GPP_64_2 | $437$ | $9.59(21)$ | $0.0(0)$ | $0.54(7)$ | $0.54(4)$ | $6.48(59)$ | $0.0(0)$ | $0.0$ | $0.5$
GPP_64_3 | $425$ | $12.5(3)$ | $0.0(0)$ | $0.42(11)$ | $0.55(12)$ | $10.5(3)$ | $0.0(0)$ | $0.4$ | $0.2$
GPP_64_4 | $407$ | $12.9(23)$ | $0.0(0)$ | $0.51(8)$ | $0.33(10)$ | $9.28(40)$ | $0.0(0)$ | $0.7$ | $0.8$
GPP_64_5 | $431$ | $10.38(31)$ | $0.0(0)$ | $0.62(5)$ | $0.57(9)$ | $8.34(48)$ | $0.0(0)$ | $0.1$ | $0.0$
Average | $-$ | $10.4$ | $0.0$ | $-$ | $-$ | $8.09$ | $0.0$ | $-$ | $-$
QKP_50_1 | $-21790$ | $334(11)$ | $0.02(1)$ | $0.56(12)$ | $0.38(5)$ | $266(58)$ | $0.02(2)$ | $0.1$ | $0.8$
QKP_50_2 | $-47302$ | $169(8)$ | $0.10(3)$ | $0.37(10)$ | $0.45(10)$ | $108(21)$ | $0.36(7)$ | $0.3$ | $0.6$
QKP_50_3 | $-58111$ | $173(95)$ | $0.48(22)$ | $0.67(4)$ | $0.43(8)$ | $0(0)$ | $1.0(0)$ | $0.6$ | $1.0$
QKP_50_4 | $-17991$ | $285(46)$ | $0.02(1)$ | $0.42(8)$ | $0.36(2)$ | $183(34)$ | $0.16(11)$ | $0.5$ | $0.3$
QKP_50_5 | $-49741$ | $214(64)$ | $0.0(0)$ | $0.82(4)$ | $0.64(10)$ | $112(14)$ | $0.008(5)$ | $0.5$ | $0.2$
Average | $-$ | $235$ | $0.12$ | $-$ | $-$ | $134$ | $0.31$ | $-$ | $-$
QKP_100_1 | $-81978$ | $114(28)$ | $0.0(0)$ | $0.52(10)$ | $0.49(10)$ | $29(6)$ | $0.06(5)$ | $0.7$ | $0.4$
QKP_100_2 | $-190424$ | $312(23)$ | $0.004(4)$ | $0.54(5)$ | $0.39(7)$ | $218(27)$ | $0.004(4)$ | $0.2$ | $0.5$
Average | $-$ | $213$ | $0.002$ | $-$ | $-$ | $124$ | $0.03$ | $-$ | $-$
|  | pQA | QA |
instance | Opt | $R_{\mathrm{50}}$ | $p_{\mathrm{suc}}$ | $R_{\mathrm{50}}$ | $p_{\mathrm{FS}}$ | $p_{\mathrm{suc}}$ |
GPP_32_1 | $91$ | $0.38(8)$ | $0.66(6)$ | $14.9(2)$ | $0.27(3)$ | $0.0(0)$ |
GPP_32_2 | $92$ | $3.2(3)$ | $0.08(1)$ | $20.5(4)$ | $0.26(5)$ | $0.0(0)$ |
GPP_32_3 | $93$ | $4.4(2)$ | $0.004(4)$ | $19.1(4)$ | $0.35(5)$ | $0.0(0)$ |
GPP_32_4 | $89$ | $2.54(19)$ | $0.12(3)$ | $17.2(3)$ | $0.33(5)$ | $0.0(0)$ |
GPP_32_5 | $104$ | $2.16(16)$ | $0.22(2)$ | $17.2(4)$ | $0.25(4)$ | $0.0(0)$ |
Average | $-$ | $2.54$ | $0.22$ | $17.8$ | $0.29$ | $0.0$ |
GPP_64_1 | $428$ | $6.0(0)$ | $0.0(0)$ | $64.3(9)$ | $0.20(2)$ | $0.0(0)$ |
GPP_64_2 | $437$ | $11.1(2)$ | $0.0(0)$ | $72.9(14)$ | $0.21(3)$ | $0.0(0)$ |
GPP_64_3 | $425$ | $14.4(1)$ | $0.0(0)$ | $56.1(9)$ | $0.21(3)$ | $0.0(0)$ |
GPP_64_4 | $407$ | $11.4(1)$ | $0.0(0)$ | $57.5(10)$ | $0.20(4)$ | $0.0(0)$ |
GPP_64_5 | $431$ | $11.0(7)$ | $0.0(0)$ | $53.3(12)$ | $0.18(3)$ | $0.0(0)$ |
Average | $-$ | $10.8$ | $0.0$ | $60.8$ | $0.20$ | $0.0$ |
QKP_50_1 | $-21790$ | $398(56)$ | $0.0(0)$ | $497(180)$ | $0.43(12)$ | $0.0(0)$ |
QKP_50_2 | $-47302$ | $164(20)$ | $0.18(7)$ | $1420(339)$ | $0.81(10)$ | $0.04(4)$ |
QKP_50_3 | $-58111$ | $37(23)$ | $0.61(24)$ | $2599(307)$ | $0.99(1)$ | $0.0(0)$ |
QKP_50_4 | $-17991$ | $272(7)$ | $0.008(4)$ | $2757(574)$ | $0.65(13)$ | $0.0(0)$ |
QKP_50_5 | $-49741$ | $179(52)$ | $0.0(0)$ | $1278(409)$ | $0.93(3)$ | $0.0(0)$ |
Average | $-$ | $210$ | $0.16$ | $1710$ | $0.762$ | $0.008$ |
QKP_100_1 | $-81978$ | $63(27)$ | $0.0(0)$ | $5286(1393)$ | $0.47(13)$ | $0.0(0)$ |
QKP_100_2 | $-190424$ | $317(49)$ | $0.0(0)$ | $1089(216)$ | $0.45(12)$ | $0.0(0)$ |
Average | $-$ | $190$ | $0.0$ | $3188$ | $0.46$ | $0.0$ |

TABLE III: Success probability of pVQA and VQA for the GPP on the gate-type
quantum device (qpu) and the simulator (cpu). Values in parentheses denote the
standard deviation.

pVQA (qpu) | VQA (qpu) | pVQA (cpu) | VQA (cpu)
---|---|---|---
$0.93(1)$ | $0.22(2)$ | $0.99(1)$ | $0.24(2)$

##  VI Discussion

The simulator result shows that the linear schedule almost reproduces the
success probability of the continuous schedule in both GPPs and QKPs. This is
expected with short or long annealing times. Because the quantum state does
not change significantly from the initial one when the annealing time is
short, the success probability is close to the random sampling with post-
processing. This situation is almost independent of the annealing path. When
the annealing time is long, the conventional quantum annealing schedule (i.e.,
linear schedule with $s_{0}=0$ and $s_{1}=1$) achieves the ground state.
Consequently, a small modification of the annealing path does not affect the
performance. However, this result is nontrivial for an intermediate annealing
time. Although the optimum annealing path for the continuous schedule is a
complicated bang-anneal-bang type (see Fig. 2 (b)), a simple linear schedule
gives a good approximation. The QAOA schedule also provides a suitable
approximation of the continuous schedule in the bang-bang regime and the bang-
anneal-bang regime. These results indicate that a small number of variational
parameters is sufficient to implement pVQA.

The experimental results on a quantum annealer demonstrate the effectiveness
of our proposed algorithm in both GPP and QKP. Because the pVQA performance
depends on the choice of the classical optimizer, it is imperative to develop
a classical optimizer that efficiently finds the optimal variational
parameters on noisy quantum devices. The gate-type quantum device shows that
pVQA outperforms the conventional QAOA. However, the experiments in this study
are limited to a small-sized problem since quantum devices with large number
of spins are not available. In the future, the pVQA performance should be
evaluated on large-sized problems.

##  VII Conclusion

We proposed pVQA to efficiently solve constrained COPs. To demonstrate its
feasibility for the state-of-the-art quantum annealer and gate-type quantum
device, we applied it to two NP-hard COPs: the graph partitioning problem and
the quadratic knapsack problem. A simulator showed that pVQA achieves an
optimal performance within a predetermined annealing time using a small number
of variational parameters. Then we experimentally verified the superior
performances of pVQA on real quantum devices compared to conventional quantum
annealing and QAOA.

## Acknowledgment

This work was supported in part by JST CREST Grant Number JPMJCR19K4, Japan
and KAKENHI Grant No.21K03391. We acknowledge the use of IBM Quantum services
for this work. The views expressed are those of the authors, and do not
reflect the official policy or position of IBM or the IBM Quantum team.

## References

  * [1] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,” _Phys. Rev. E_ , vol. 58, pp. 5355–5363, Nov 1998.
  * [2] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum computation by adiabatic evolution,” _arXiv:quant-ph/0001106_ , 2000. [Online]. Available: https://arxiv.org/abs/quant-ph/0001106
  * [3] S. Morita and H. Nishimori, “Convergence of quantum annealing with real-time schrödinger dynamics,” _Journal of the Physical Society of Japan_ , vol. 76, no. 6, p. 064002, 2007. [Online]. Available: https:{/}{/}doi.org{/}10.1143{/}JPSJ.76.064002
  * [4] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, “Quantum annealing with manufactured spins,” _Nature_ , vol. 473, no. 7346, pp. 194–198, 2011.
  * [5] M. Maezawa, G. Fujii, M. Hidaka, K. Imafuku, K. Kikuchi, H. Koike, K. Makise, S. Nagasawa, H. Nakagawa, M. Ukibe, and S. Kawabata, “Toward practical-scale quantum annealing machine for prime factoring,” _Journal of the Physical Society of Japan_ , vol. 88, no. 6, p. 061012, 2019.
  * [6] A. D. King, S. Suzuki, J. Raymond, A. Zucca, T. Lanting, F. Altomare, A. J. Berkley, S. Ejtemaee, E. Hoskinson, S. Huang, E. Ladizinsky, A. J. R. MacDonald, G. Marsden, T. Oh, G. Poulin-Lamarre, M. Reis, C. Rich, Y. Sato, J. D. Whittaker, J. Yao, R. Harris, D. A. Lidar, H. Nishimori, and M. H. Amin, “Coherent quantum annealing in a programmable 2,000 qubit Ising chain,” _Nature Physics_ , vol. 18, no. 11, pp. 1324–1328, 2022. [Online]. Available: https:{/}{/}doi.org{/}10.1038{/}s41567-022-01741-6
  * [7] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, “The unconstrained binary quadratic programming problem: a survey,” _Journal of Combinatorial Optimization_ , vol. 28, no. 1, pp. 58–81, 2014. [Online]. Available: https:{/}{/}doi.org{/}10.1007{/}s10878-014-9734-0
  * [8] J. Roland and N. J. Cerf, “Quantum search by local adiabatic evolution,” _Phys. Rev. A_ , vol. 65, p. 042308, Mar 2002. [Online]. Available: https:{/}{/}link.aps.org{/}doi{/}10.1103{/}PhysRevA.65.042308
  * [9] R. D. Somma, D. Nagaj, and M. Kieferová, “Quantum speedup by quantum annealing,” _Phys. Rev. Lett._ , vol. 109, p. 050501, Jul 2012. [Online]. Available: https:{/}{/}link.aps.org{/}doi{/}10.1103{/}PhysRevLett.109.050501
  * [10] L. Fry-Bouriaux, D. T. O’Connor, N. Feinstein, and P. A. Warburton, “Locally suppressed transverse-field protocol for diabatic quantum annealing,” _Phys. Rev. A_ , vol. 104, p. 052616, Nov 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.104.052616
  * [11] S. Matsuura, S. Buck, V. Senicourt, and A. Zaribafiyan, “Variationally scheduled quantum simulation,” _Phys. Rev. A_ , vol. 103, p. 052435, May 2021\. [Online]. Available: https:{/}{/}link.aps.org{/}doi{/}10.1103{/}PhysRevA.103.052435
  * [12] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” _arXiv:1411.4028_ , 2014.
  * [13] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,” _Phys. Rev. X_ , vol. 10, p. 021067, Jun 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevX.10.021067
  * [14] Y. Susa and H. Nishimori, “Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme,” _Phys. Rev. A_ , vol. 103, p. 022619, Feb 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.103.022619
  * [15] J. Côté, F. Sauvage, M. Larocca, M. Jonsson, L. Cincio, and T. Albash, “Diabatic quantum annealing for the frustrated ring model,” _arXiv:2212.02624_ , 2022.
  * [16] J. R. Finžgar, M. J. Schuetz, J. K. Brubaker, H. Nishimori, and H. G. Katzgraber, “Designing quantum annealing schedules using Bayesian optimization,” _arXiv:2305.13365_ , 2023.
  * [17] A. Lucas, “Ising formulations of many NP problems,” _Frontiers in Physics_ , vol. 2, p. 5, 2014.
  * [18] T. Shirai and N. Togawa, “Multi-spin-flip engineering in an Ising machine,” _IEEE Transactions on Computers_ , pp. 1–1, 2022.
  * [19] M. Kuramata, R. Katsuki, and K. Nakata, “Larger sparse quadratic assignment problem optimization using quantum annealing and a bit-flip heuristic algorithm,” in _2021 IEEE 8th International Conference on Industrial Engineering and Applications (ICIEA)_ , 2021, pp. 556–565.
  * [20] K. Fukada, M. Parizy, Y. Tomita, and N. Togawa, “A three-stage annealing method solving slot-placement problems using an Ising machine,” _IEEE Access_ , vol. 9, pp. 134 413–134 426, 2021.
  * [21] F. Glover, G. Kochenberger, and Y. Du, “A tutorial on formulating and using QUBO models,” _arXiv:1811.11538_ , 2018. [Online]. Available: https:{/}{/}arxiv.org{/}abs{/}1811.11538
  * [22] T. Shirai and N. Togawa, “Spin-variable reduction method for handling linear equality constraints in Ising machines,” _IEEE Transactions on Computers_ , vol. 72, no. 8, pp. 2151–2164, 2023.
  * [23] K. Tanahashi, S. Takayanagi, T. Motohashi, and S. Tanaka, “Application of Ising machines and a software development for Ising machines,” _Journal of the Physical Society of Japan_ , vol. 88, no. 6, p. 061010, 2019\.
  * [24] P. Díez-Valle, D. Porras, and J. J. García-Ripoll, “Quantum variational optimization: The role of entanglement and problem hardness,” _Phys. Rev. A_ , vol. 104, p. 062426, Dec 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.104.062426
  * [25] L. T. Brady, C. L. Baldwin, A. Bapat, Y. Kharkov, and A. V. Gorshkov, “Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems,” _Phys. Rev. Lett._ , vol. 126, p. 070505, Feb 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.126.070505
  * [26] S. Edelkamp and S. Schrödl, “Chapter 13 - constraint search,” in _Heuristic Search_ , S. Edelkamp and S. Schrödl, Eds. San Francisco: Morgan Kaufmann, 2012, pp. 571–631. [Online]. Available: https:{/}{/}www.sciencedirect.com{/}science{/}article{/}pii{/}B9780123725127000134
  * [27] D. Pisinger, “The quadratic knapsack problem—a survey,” _Discrete Applied Mathematics_ , vol. 155, no. 5, pp. 623–648, 2007. [Online]. Available: https:{/}{/}www.sciencedirect.com{/}science{/}article{/}pii{/}S0166218X06003878
  * [28] T. Yoshimura, T. Shirai, M. Tawada, and N. Togawa, “QUBO matrix distorting method for consumer applications,” in _2022 IEEE International Conference on Consumer Electronics (ICCE)_ , 2022, pp. 01–06.
  * [29] Y. Mukasa, Y. Matsuda, S. Tanaka, and N. Togawa, “Scalable algorithms for capacitated vehicle routing problem using Ising machines,” in _Adiabatic Quantum Computing Conference 2021_ , 2021. [Online]. Available: https:{/}{/}aqc2021.org{/}poster2{/}b{/}B6.pdf
  * [30] K. Tamura, T. Shirai, H. Katsura, S. Tanaka, and N. Togawa, “Performance comparison of typical binary-integer encodings in an Ising machine,” _IEEE Access_ , vol. 9, pp. 81 032–81 039, 2021.
  * [31] C. Patvardhan, S. Bansal, and A. Srivastav, “Solving the 0–1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm,” _Journal of Computational and Applied Mathematics_ , vol. 285, pp. 86–99, 2015. [Online]. Available: https:{/}{/}www.sciencedirect.com{/}science{/}article{/}pii{/}S0377042715000862
  * [32] Fixstars Amplify AE. [Online]. Available: https:{/}{/}amplify.fixstars.com{/}en{/}engine
  * [33] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors, “SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python,” _Nature Methods_ , vol. 17, pp. 261–272, 2020.
  * [34] R. Wiersema, C. Zhou, Y. de Sereville, J. F. Carrasquilla, Y. B. Kim, and H. Yuen, “Exploring entanglement and optimization within the hamiltonian variational ansatz,” _PRX Quantum_ , vol. 1, p. 020319, Dec 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PRXQuantum.1.020319
  * [35] K. Boothby, P. Bunyk, J. Raymond, and A. Roy, “Next-generation topology of D-wave quantum processors,” in _D-Wave Technical Report Series_ , no. 14-1026A-C, 2019.
  * [36] IBM Quantum. [Online]. Available: https:{/}{/}quantum-computing.ibm.com
  * [37] V. Choi, “Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,” _Quantum Information Processing_ , vol. 7, no. 5, pp. 193–209, 2008.
  * [38] ——, “Minor-embedding in adiabatic quantum computation: II. minor-universal graph design,” _Quantum Information Processing_ , vol. 10, no. 3, pp. 343–353, 2011.
  * [39] Qiskit contributors, “Qiskit: An open-source framework for quantum computing,” 2023.


Torelli for elliptic surfaces]
Generic Torelli with denominators for
elliptic surfaces
N. I. Shepherd-Barron
King's College,
London WC2R 2LS,

We show that a very general Jacobian
elliptic surface is determined by its polarized
$\Q$-Hodge structure, subject to various constraints
on the irregularity and the geometric genus.

AMS classification: 14C34, 32G20.
We consider the stack $\sje_{h,q}$ of Jacobian elliptic surfaces
$f:X\to C$ over $\C$
of geometric genus $h$ and irregularity $q$,
provided that $8h> 10(q-1)$ and
$h\ge q+3$.
If all the singular fibres are of Kodaira type $I_1$
then the datum of such a surface is equivalent to the datum of
a classifying morphism $\Phi:C\to \bsell$ from $C$ to the stack
$\bsell$ of generalized elliptic curves.

In <cit.> we showed that then the derivative of the period map
associated  to the primitive cohomology $H^2_{prim}(X)$,
which is defined as the orthogonal complement
of a fibre and the zero section,
determines the base curve $C$, the ramification divisor
$Z=\Ram_\Phi$ in $C$  of $\Phi$ and the
copy of $C$ in $\P^{h-1}$ that arises as the image of $X$
under the linear system
$\vert K_X\vert = f^*\vert K_C+\Phi^*M\vert$.
(Here $M$ is the bundle  of weight one modular forms on $\bsell$
and, under our assumptions, $\vert K_X\vert$ has no
base points, so that the infinitesimal Torelli
theorem holds for these surfaces.)
We went on to show
that if also $q\ge 2$ and the pair $(C,Z)$ is generic
(as we assume for the rest of this paper)
then these data determine $\Phi$ modulo the automorphism group
$\GG_m$ of $\bsell$. We then proved, without the assumption
that $q\ge 2$, that the generic Torelli theorem holds for these
In this paper we consider such surfaces under the
assumptions that

\begin{eqnarray}\label{assume}
8h>10(q-1),\ h\ge q+3\ \textrm{and}\ q\ge 2&{}&
\end{eqnarray}

and we show that
a very general such surface $f:X\to C$
is determined by its polarized $\Q$-Hodge structure.
To do so it is enough, given the results that we have just
to assume that the base curve $C$ and the line bundle
$L=\Phi^*M$ on $C$ are fixed and to
consider only surfaces in the $\GG_m$-orbit
of the point defined by $f:X\to C$ in the closed substack
$\sje_{C,L}$ of the stack
$\sje=\sje_{h,q}$ of these surfaces.

Recall ([7], p. 28) that
$X$ is embedded as a divisor
in the $\P^2$-bundle

$$\pi:\P=\P_{C,L}=\P(\sO\oplus L^{2}
\oplus L^{3})\to C$$

and is linearly equivalent to the line bundle
It is defined by an

$$Y^2Z = 4X^3 +g_4 XZ^2 + g_6 Z^3$$

where $g_n\in H^0(C, L^{\otimes n})$.
If $g_6=0$ then $X$ is a Gauss surface
and if $g_4=0$ then $X$ is an Eisenstein surface
because in that case $X$ has an action by
$\Z/4$ or $\Z/6$, respectively. In the Eisenstein
case the action of $\langle\a\rangle=\Z/6$
is given by $\a^*(X,Y,Z)=(\zeta_6^2 X, \zeta_6^3Y, Z)$.

The closure of the $\GG_m$-orbit
through $X$ is the pencil $\{X_{(\lambda,\mu)}\}_{(\lambda,\mu)\in\P^1}$
given by the equation

$$Y^2Z = 4X^3 +\lambda g_4 XZ^2 + \mu g_6 Z^3,$$

where $\lambda,\mu$
are homogeneous co-ordinates on the
copy of $\P^1$ that is the closure of $\GG_m$.
We call this the Gauss–Eisenstein pencil
through $X$ and regard it as a canonically defined
pencil through
$X$ that is generated by the Eisenstein surface $X_6$
defined by $\lambda=0$ and the Gauss
surface $X_4$ defined by
$\mu=0$. The surfaces $X_6$ and $X_4$ are determined
by $X$, since they are the fixed points in the closure of
the $\GG_m$-orbit through $X$.
When $g_6$ has isolated zeroes then $X_6$
is smooth and when $g_6$ has a double
zero then $X_6$ has a singularity of type $A_2$.

Until now we have only considered general surfaces in $\sje$.
The condition that the surface be general excludes Gauss and Eisenstein
To include them, we consider the stack $\sje^{RDP}$
whose geometric points are relative canonical models
of Jacobian elliptic surfaces. (These are the surfaces
with RDPs that arise from contraction of the vertical
$(-2)$-curves that are disjoint from the zero section.
For such surfaces there
might be no classifying morphism $\Phi:C\to\bsell$,
but there is still a zero section and its conormal bundle,
so it makes sense to speak of
the closed substack $\sje^{RDP}_{C,L}$ of $\sje^{RDP}$.)
The Gauss–Eisenstein pencils are in these
stacks $\sje^{RDP}_{C,L}$. If $\sD$ is the relevant
period domain (in the context of this paper it classifies Hodge structures on
$H^2_{prim}(Y,\Z)$ when $Y$ is a Jacobian elliptic surface
of geometric genus $h$ and irregularity $q$)
and $\G$ the relevant arithmetic group
then the period map
exists as a morphism

$$per:[\sje^{RDP}]\to [\sD/\G]$$

of geometric quotients; here, and for the
rest of this paper, $[\sX]$ denotes
the geometric quotient of the Deligne–Mumford stack
$\sX$ in either of the algebraic or the analytic contexts.

Eisenstein surfaces
Fix both a curve $C$ (of
genus $q\ge 0$) and a line bundle $L$ on it of degree $h+1-q>0$.
We consider Jacobian elliptic surfaces $X\to C$ such that
$p_g(X)=h$ and
$L$ is the conormal bundle of the zero section.
Note that $L$
also the pull-back $\Phi^*M$ of the bundle of
weight $1$ modular forms.
If $L$ is generic then $6L$
is very ample.
This follows from the assumptions that
$8h> 10(q-1)$ and $h\ge q+3$.

We shall consider more particularly the corresponding family
$\{X_t\}$ of Eisenstein surfaces defined by $g_4=0$; the parameter
space is the linear system $\vert 6L\vert$. We put
$V=H^2_{prim}(X_{\bareta}, \Q)$,
where $X_{\bareta}$ is the geometric generic
member of this family, and let $G$
denote the monodromy group acting on $V$.
The action of $\g =\a^2$ on $X_{\bareta}$
$V$ into a $\Q[T]/(T^3-1)$-module and then
$G$ is a group of $\Q[T]/(T^3-1)$-linear transformations
of this module.
In this section we re-write that part (4.4) of [6]
that is concerned with monodromy in even
fibre dimension in this context.

Take a general pencil $\Pi$ in $\vert 6L\vert$.
Since $6L$ is very ample
this gives a family

$$a:\sX\to\Pi\cong \P^1$$
whose total space $\sX$ is a
smooth blow-up of $\P_{C,L}$ and
whose geometric generic member
$X_{\bareta}$ is smooth. Moreover, again because
$6L$ is very ample, each of the
finitely many singular fibres
has a single $A_2$-singularity.
Note that $V$ is identified with the orthogonal
complement of the image of $H^2(\sX,\Q)$
in $H^2(X_{\bareta},\Q)$.

Let $F$ denote a local Milnor fibre in this family,
so that $H^2(F,\Q)$ is the $\Q$-module
spanned by roots $\delta_1,\delta_2$ such that
$\delta_i^2=-2$ and $\delta_1.\delta_2 = 1$.
the local monodromy operator $\s$ on $H^2(F,\Q)$
is a Coxeter element in the Weyl group $W(A_2)$,
so is of order $3$.
We shall refer to these roots $\delta_i$
as the basic cycles and to the Coxeter elements
$\s$ as basic transformations.

By letting $\Pi$
move in the Grassmannian of lines in $\vert 6L\vert$
we see, as in [8] XVIII,
that the basic transformations
form a single conjugacy class in
$G$ and they
generate $G$.

Since the fibres of $\sX\to \Pi$ all have only du Val
singularities, they satisfy the hypotheses of
Théorème 1.1 of [8] XVIII, so that
the Leray spectral sequence

$$E_2^{pq}=H^p(\Pi, R^qa_*\Q) \Rightarrow

degenerates at $E_2$. From this it follows
$H^2_{prim}(X_{\bareta},\Q)^G$ consists of classes that
come from the threefold $\sX$
and the lemma is proved.

The action of $\g$ on $H^2(F,\Q)$
is non-trivial.
$F$ is the affine surface
defined by the equation $xy+z^3=1$
and $\g$ acts as $\g^*(x,y,z)=(x,y,\zeta_6^4 z)$.
So the fixed locus of $\g$ in $F$ is $\C -\{0\}$,
whose Euler characteristic is zero.
We conclude by the Lefschetz fixed point theorem.

It follows that the action of
$\g$ on $H^2(F,\Q)$ is given by

Recall that $\Z/3=\langle\g\rangle$ has just two irreducible
representations over $\Q$, namely, the trivial
$V_0=\Q$ and the $2$-dimensional representation
$V_1=\Q(\zeta_3)$, on which $\g$ acts as multiplication by
In particular, $H^2(F,\Q)$ is isomorphic to $V_1$; in other words,
$H^2(F,\Q)$ is a $1$-dimensional $\Q(\zeta_3)$-vector space and as
such is generated
by a basic cycle.

The next lemma is well known.
If $A$ and $B$ are groups, $k$ is a field
and $W$ is a representation of $A\times B$ defined
over $k$ on which the action of $A$ is completely
reducible, then there is a decomposition

$$W=\oplus_j\left( V_j\otimes_k U_j\right)$$

of $k[A\times B]$-modules,
where $V_j$ runs over the irreducible representations
of $A$ defined over $k$ and
$U_j$ is the representation of $B$ given by

Taking $k=\Q$,
$A=\langle\g\rangle$, $B=G$ and $W=V$ gives
$V=(V_0\otimes U_0) \oplus (V_1\otimes U_1)$
for some representations $U_0, U_1$ of $G$.
$V_0\otimes U_0=V^\g=0$.
That $V_0\otimes U_0= V^\g$
follows from the definition of $U_0$ and $V_0$, while $V^\g$
is also the primitive cohomology
of the geometric quotient $[X/\g]$.
This is a $\P^1$-bundle over $C$, so that
its primitive cohomology is zero.

$V$ is naturally a representation
of $G$ defined over $\Q(\zeta_3)$.
We already know that $V$ is a $\Q[T]/(T^3-1)$-module
and we have just shown that the eigenspace belonging
to $T=1$ is zero.

The intersection pairing $b:V\times
V\to \Q$
is $\Q$-bilinear,
and $\g\times G$-invariant. Write
and define
$B:V\times V \to \Q(\zeta_3)$ by

$$B(u,v)=\theta^{-1}\left(\zeta_3 b(u,v)-
b(u,\zeta_3 v)\right);$$

then $B$ is a
$G$-invariant Hermitian $\Q(\zeta_3)$-sesquilinear form
and $b=\tr_{\Q(\zeta_3)/\Q}B$.

Let us say that the signature of $B$ is $(p,r)$;
then the signature of $b$ is $(2p,2r)$.
We are dealing with elliptic surfaces of
geometric genus $h$ and irregularity $q$, so that $p=h$
and $r=4(h+1-q)$.
So $p\ge 0$ and $r\ge 4$. In particular,
$\dim_{\Q(\zeta_3)}V\ge 4$.

Define a root to be any $G$-conjugate of a basic
cycle. Then, for every root $\delta$, $B(\delta,\delta)=-1$ and
the corresponding complex reflexion $\s=\s_\delta$ is given by
the formula

$$\s_\delta(x)=x+(1-\zeta_3) B(x,\delta)\delta.$$

This shows that $\s_\delta$ acts as a unitary reflexion of
order $3$.
The unitary group $U_B$ is an algebraic group
defined over $\Q$ and has a determinant homomorphism

$$\det :U_B\to R^1_{\Q(\zeta_3)/\Q}\GG_m$$

that is also defined over $\Q$;
here $R^1_{\Q(\zeta_3)/\Q}\GG_m$ is the kernel of the norm
homomorphism $R_{\Q(\zeta_3)/\Q}\GG_m\to\GG_m$.
The kernel of $\det$ is $SU_B$. The centre of $U_B$ is
isomorphic to $R^1_{\Q(\zeta_3)/\Q}\GG_m$. Since each
$\s_\delta$ lies in $U_B$ it follows that $G\subseteq U_B$
and that therefore $M\subseteq U_B$.

$V$ is an absolutely irreducible $\Q(\zeta_3)[G]$-module.
Moreover, $V$ is spanned,
as a $\Q(\zeta_3)$-vector space, by
the $G$-orbit of any root.

Note first that $(V_\R)^G
=(V^G)\otimes_{\Q(\zeta_3)}\C=0$, by Lemma <ref>,
and that $B$ extends
to a Hermitian form on $V_\R$.

Suppose that $V'$ is a non-zero
sub-$\C[G]$-module of $V_\R$.
If there is a root $\delta$ such that
$V'\subseteq Fix(\s_\delta)$, then

$$V'=g(V')\subseteq Fix(g\s_\delta g^{-1})$$

for all $g\in G$, so that,
since the $G$-conjugates
of $\s_\delta$ generate $G$,
$V'\subseteq (V_\R)^G=0$.
So every
$\s_\delta$ acts non-trivially on $V'$.

Fix a root $\delta$ and choose $x\in V'$ such that
$\s_\delta(x)\ne x$.
Then the formula defining $\s_\delta$ shows
that $\delta\in V'$. Let $P$
be the $\C$-subspace of $V_\R$ spanned by
the cycles $\delta$; then $P$ is a
non-zero $\C[G]$-module
and $P$ is contained in every non-zero
sub-$\C[G]$-module $V'$ of $V_\R$.
In particular, $P$ is irreducible.

Now suppose that $P^\perp\ne 0$. Then
$P\subseteq P^\perp$. However, $\delta\in P$
and $B(\delta,\delta)\ne 0$, so $P^\perp =0$.
Therefore $P=V_\R$ and the lemma follows.

Now let $M$ denote the algebraic subgroup,
over $\Q$, of the unitary group $U_B$
that is generated by $G$. Since $G$ is generated by a
single conjugacy class of unitary reflexions of order $3$,
the same is true of $M$. Let
$\tmu_n\subset R^1_{\Q(\zeta_3)/\Q}\GG_m$ be the $n$-torsion
subgroup; this is the quadratic twist of $\mu_n$ determined by
So $\det^{-1}(\tmu_3)$ is an extension of $\tmu_3$ by
$SU_B$; we denote this group by $SU_B.\tmu_3$.

Either $M=SU_B.\tmu_3$
or $G$ is finite.
Observe first that
$M\subseteq SU_B.\tmu_3$ since
$G$ is generated by elements of order $3$.

We set up some notation, as follows.

* $\tM=R^1_{\Q(\zeta_3)/\Q}\GG_m.M\subset U_B$.

* $\Sigma\subset V_\R$
is the real
quadric hypersurface in $V_\R$
defined by $B(x,x) =-1$.

* Take any root $\delta_0$
and let $\tR$ denote its $\tM(\R)$-orbit
and $R$ its $M(\R)$-orbit; these orbits
are independent of the choice of $\delta_0$
and are real semi-algebraic subsets of $\Sigma$.

* Given $\delta,\eta\in \tR$ that are not $\C$-proportional,
let $L_{\delta,\eta}$ denote the complex $2$-plane
that they span and let $H_{\delta,\eta}$ denote the real
algebraic subgroup
of $M_{\R}$ generated by $\s_\delta,\s_\eta$.

Note that if $\delta\in\tR$ then $\delta=\lambda\eta$
for some $\eta\in R$ and $\lambda\in\C$ with
$\vert\lambda\vert =1$, so that we can define
$\s_\delta$ by $\s_\delta=\s_\eta$. So $\s_\delta$
is defined for all $\delta\in\tR$ and is a unitary
reflexion of
order $3$. Also $H_{\delta,\eta}$
acts on $L_{\delta,\eta}$ as a group of unitary transformations
and projects to a subgroup $P H_{\delta,\eta}$
of the corresponding projective unitary group
acting on $\P(L_{\delta,\eta}^\vee)=

Assume that $\delta, \eta\in\tR$
and are not $\C$-proportional.

[i] If
$\vert B(\delta,\eta)\vert >1$
then $P H_{\delta,\eta}=PSU(1,1)\cong PSL_2(\R)$.

[ii] If
$\vert B(\delta,\eta)\vert <1$
then, except for finitely many
values of $\vert B(\delta,\eta)\vert$,
$P H_{\delta,\eta}=PSU(0,2)\cong SO_3(\R)$.

[iii]  If
$\vert B(\delta,\eta)\vert =1$
then $P H_{\delta,\eta}$ is a non-trivial
split extension $\C\rtimes\Z/3$,
regarded as a $2$-dimensional
real algebraic group.

There is a finite subset $\sC$ of the interval
$[0,1)$ such that, if
$\vert B(\delta,\eta)\vert\not\in \sC$, the group
$P H_{\delta,\eta}$ is either $PSU(1,1)$ or
$PSU(0,2)$ or  $\C\rtimes\Z/3$.
We start with the
classification of the real algebraic subgroups
of $PSU_\b$, where $$̱ is a
non-zero Hermitian
form on a $2$-dimensional
complex vector space of signature
$(0,2),\ (1,1)$ or $(0,1)$, that
are generated by elements of order $3$.
In turn, this derives from the classification
of the algebraic subgroups $H$ of
the algebraic group $PSL_{2,\C}$ over $\C$.
The fact that $3$ is odd simplifies matters.

The algebraic subgroups $H$ of $PSL_{2,\C}$ are:
$PSL_{2,\C}$ itself; subgroups of
the normalizer of a maximal torus;
subgroups of a Borel subgroup $B$;
polyhedral subgroups
${\mathfrak A}_4,{\mathfrak S}_4$ and
${\mathfrak A}_5$. So if $H$ is the Zariski
closure of a group
generated by elements of order $3$ then $H$ is one
of: $PSL_{2,\C}$; $\Z/3$; a non-trivial
extension of $\Z/3$ by
the unipotent radical $U\cong\C$ of $B$;
${\mathfrak A}_4$ or ${\mathfrak A}_5$.

* It follows that any real algebraic subgroup $K$ of
$PSU(1,1)\cong PSL_2(\R)$ that is the Zariski
closure of a group generated by elements
of order
$3$ is either $\Z/3$ or $PSL_2(\R)$.
The fact that
$\delta$ and $\eta$ are not proportional
shows that $P H_{\delta,\eta}\ne\Z/3$.

* The analogous
subgroups of $PSU(0,2)\cong SO_3(\R)$ are $SO_3(\R)$,
$\Z/3$, ${\mathfrak A}_4$ and ${\mathfrak A}_5$.
The cases of
${\mathfrak A}_4$ and ${\mathfrak A}_5$ are excluded
by excluding finitely many
values of $\vert B(\delta,\eta)\vert$
because we need to consider
the situation
where $\delta,\eta$ are vertices of a
spherical triangle with angles $\pi/3,\pi/3$
at $\delta,\eta$. The exceptional
cases are those where the third angle
is a rational multiple $a\pi/b$ of $\pi$,
$1/3<a/b<1$ and
$b\le 5$. It is clear that
this can only happen for finitely many values
of $\vert B(\delta,\eta)\vert$, all of which lie in
$[0,1)$. As before, $\Z/3$ is excluded
by the fact that $\delta, \eta$ are not proportional.

* In the degenerate case
where $\vert B(\delta,\eta)\vert =1$, we see similarly
that $PH_{\delta,\eta}$ is a non-trivial
split extension of $U$ by $\Z/3$.

Finally, iv follows from

If $\delta, \eta\in\tR$ are $\C$-proportional then
$\s_\delta=\s_\eta^\pm$, so they generate
a copy of $\Z/3$.

Suppose that
$\vert B(\delta,\eta)\vert\not\in \sC$
and that $\delta,\eta$ are not $\C$-proportional.
Define $O_{\delta,\eta}$ to be the
$H_{\delta,\eta}$ orbit of $\delta$
in the complex $2$-plane $L_{\delta,\eta}$. Then
$L_{\delta,\eta}^0=\C^*.O_{\delta,\eta}$ is a dense
subset (in the real sense)
of $L_{\delta,\eta}$
and $L_{\delta,\eta}^0\cap \Sigma\subseteq \tR$.
This follows at once from Lemma <ref>.

Suppose that $W\subseteq V_\R=V\otimes_{\Q(\zeta_3)}\C$ is a
sub-$\C$-vector space containing
a dense semi-algebraic subset
$W^0$ such that

* $W^0\cap\Sigma$
is non-empty,

* $W^0\cap \Sigma$ is dense in $W\cap \Sigma$ and

* $W^0\cap\Sigma$ is contained in $\tR$.

In particular, $W$ is spanned by $W\cap\tR$.

For example, the one-dimensional
such subspaces are exactly the
lines $\C\delta$, where $\delta\in R$,
and, provided that $\delta,\eta$ are not proportional
and $\vert B(\delta,\eta)\vert\not\in \sC$ ,
the complex $2$-plane $L_{\delta,\eta}$ is another.

Assume until the end of the proof of
Theorem <ref>
that $W$ is maximal with respect to these properties.
So certainly $W\ne 0$.

Assume that $W\ne V_\R$. Then
$G$ is finite.

Note first that $\tR\setminus W$ is not empty, since
$\tR$ generates $V_\R$.

We proceed to establish
Lemmas <ref> and <ref>.

Suppose that $\delta\in\tR\setminus W$.
Then the
function $\b_\delta:W\to\R$
defined by $\b_\delta(x)=\vert B(x,\delta)\vert$
only takes values in $\sC$ when restricted
to $W\cap\tR$.

Suppose that $\eta\in W\cap\tR$ (so that,
in particular, $\eta$ is not $\C$-proportional to
$\delta$) and that
$\vert B(\delta,\eta)\vert\not\in \sC$.
Then $L_{\delta,\eta}^0\cap\Sigma\subseteq \tR$. Now
let $\eta$ vary over the subset $\sS_1$ of
$W\cap\tR$ defined by the conditions that
$\vert B(\delta,\eta)\vert\not\in \sC$
and $\eta$ is not proportional to $\delta$.
This is a semi-algebraic set.
Put $\sS_2=\cup_{\eta\in U_1}L_{\delta,\eta}^0$,
so that

Moreover, $\sS_2$ is semi-algebraic;
this can be seen
by defining the semi-algebraic
subset $\sS_3$ of $\sS_1\times M(\R)$ by

$$\sS_3=\{(\eta,m) \vert \eta\in \sS_1\ \textrm{and}\ m\in H_{\delta,\eta}\}$$

and observing that $\sS_2$
is the image of $\C^*\times \sS_3$ under the map

$$\C^*\times \sS_3 \to V\ :\ (z,\eta,m)
\mapsto z.m(\eta).$$

Since $L^0_{\delta,\eta}$ is dense in
$L_{\delta,\eta}$, it follows that
$\sS_2$ is dense in $\cup_{\eta\in U_1}L_{\delta,\eta}$
and so is dense in $W\oplus\C\delta$.
we can enlarge $W$ to $W\oplus\C\delta$
and then take $(W\oplus\C\delta)^0=\sS_2$ to
contradict the maximality of $W$.

[i] Suppose that
$\delta\in\tR\setminus W$.
Then either
$\delta\in W^\perp$
$W\cap W^\perp$ is of $\C$-codimension
one in $W$. In both cases $\delta$ is orthogonal
to $W\cap W^\perp$.

$W\cap W^\perp=0$.

$$W\cap\tR\supseteq W\cap W^0\cap\Sigma =W^0\cap\Sigma,$$

so that, by Lemma <ref>,
$\b_\delta$ takes values only in the finite set
$\sC$ on the non-empty
dense semi-algebraic subset
$W^0\cap\Sigma$ of $W\cap\Sigma$.
Therefore $\b_\delta$ takes values only in $\sC$
on the real quadric hypersurface

Fix $c\in \sC$ and consider the condition that
for $w\in W$.
There are complex co-ordinates $(z_k)_{k\in K}$ on $W$
and disjoint subsets $I,J$ of $K$ such that
$J$ is not empty,
$W\cap\Sigma$ is given by the equation $D=0$,

$$D=\sum_{i\in I}\vert z_i\vert^2 -
\sum_{j\in J}\vert z_j\vert^2+1,$$

and the condition that $\b_\delta(w)=c$ is given by the equation
$E=0$, where

$$E=\vert B(z,\delta)\vert^2-c^2.$$

Then $dD$ is proportional to $dE$ on $W\cap\Sigma$.
Say $dE=\phi dD$ on $W\cap\Sigma$
for some function $\phi$ on $W\cap\Sigma$.
Write  $B(w,\delta)=\sum_{i\in I} a_iz_i-\sum_{j\in J} a_jz_j
+\sum_{k\not\in I\cup J} b_k z_k.$

$$\bar{a}_k B(w,\delta)=\phi z_k$$

on $W\cap \Sigma$
for all $k\in I\cup J$.
This gives two possibilities: either

* the function $w\mapsto B(w,\delta)$ is identically zero
on $W\cap\Sigma$ (in which case it vanishes
on $W$ and $\delta\in W^\perp$) or

* $I$ is empty,
$J$ has just one element,
$W\cap\Sigma$ is the cone $\widehat{\Sigma}$
a circle $\vert z\vert^2=1$
and the restriction of $\b_\delta$ to $W\cap\Sigma$
is proportional to $\vert z\vert$.

In the first case $\delta\in W^\perp$.
in the second case $\b_\delta$
vanishes on the vertex
of $\widehat{\Sigma}$ and this vertex has codimension
$1$ in $W$. Moreover, this vertex is $W\cap W^\perp$,
and part $(1)$ of the lemma is
Note that $\delta$ is orthogonal
to $W\cap W^\perp$, from $(1)$.
Then $W\cap W^\perp$ is orthogonal
to every root in $W$ and to every root not in $W$,
so lies in $V_\R^G$. But this space vanishes,
by Lemma <ref>, and the lemma is proved.

Now we finish the proof of Proposition

First, suppose that $\dim_\C W\ge 2$. Then,
by Lemma <ref>, $\tR\setminus W\subseteq W^\perp$,
so that for every root in $\tR\setminus W$
the reflexion $\s_\delta$ preserves $W$.
Certainly $\s_\delta$ preserves $W$ for every
root $\delta$ in $W$, so that $W$ is $G$-invariant.
But $V_\R$ is irreducible and $W\ne V_\R$, so
we have a contradiction and $\dim_\C W=1$.

Next, since $W\cap\tR$ is not empty, $W\cap R$ is also non-empty
and then $W$ is a line $\C\delta$ for some $\delta\in R$.

Next, let $\tM^0$ denote the identity
connected component of $\tM$
and $\tR^0=\tM^0(\R)\delta_0$.
Then, for all $\delta\in\tR^0$
and for all $m\in\tM^0(\R)$ close to
the identity,
$\vert B(\delta, m(\delta))\vert$
is close to $1$ and so does not lie in $\sC$.
Therefore $\delta$ and $m(\delta)$
proportional, since otherwise $L_{\delta,\eta}$
would be a $2$-dimensional space $W$. So $\tM^0$
preserves each
complex line $W$.
Since the lines $\C\delta$ span $V_\R$,
it follows that $\tM^0$ is a real algebraic torus
and that $V_\R$ decomposes as a
direct sum
$V_\R=\oplus U_\chi$,
where $\chi$ runs over the complex characters
of $\tM^0$ and $U_\chi$ is the
$\chi$-eigenspace of $V_\R$.

Finally, suppose that $r$ is the number of distinct
characters in this decomposition
and that $r\ge 2$.
Since $\tM^0$ is normal
in $\tM$, this decomposition is
a system of imprimitivity for
the action of $\tM$ on $V_\R$,
and so for the group $G$.
However, if $G$ were imprimitive
then it would, since the representation
$V_\R$ is irreducible, possess
a surjection onto the symmetric group
${\frak S}_r$ ([22], penultimate
paragraph of
p. 276; at this point of their paper
the assumptions that the group
in question be finite and unitary are not relevant).
Since $G$ is generated
by elements of odd order
this is impossible, so that
$r=1$ and $\tM^0$ is $1$-dimensional. Since $\tM^0$ contains $S^1$
it is then equal to $S^1$, which is
the centre of $U_B$. But
$M\subseteq SU_B.\tmu_3$,
so $M$ is finite
and Proposition <ref>
is proved.

Assume that
$W=V_\R$. Then $M=SU_B.\tmu_3$.
Since $W=V_\R$, it follows that
so that $\tR$ is dense in $\Sigma$.
Therefore $M(\R)$ equals the
real algebraic subgroup
$N$ of $U_B(\R)$ that is generated by the
unitary reflexions of the form

$$x\mapsto x+(1-\zeta_3)B(x,\delta)\delta,$$

as $\delta$ runs over the elements of
$\Sigma$. It is clear that $N$
is normal in $U_B(\R)$ and is contained in
$(SU_B.\tmu_3)(\R)$. Since $SU_B(\R)$ is a simple
real algebraic group, it follows that
$M(\R) =(SU_B.\tmu_3)(\R)$ and
the proposition is proved.

This completes the proof of Theorem <ref>.

If $G$ is finite then
$h=q=0$ and $G$ is the group
$G=W(L_4)$ (the group
in the list constructed by
Shephard and Todd [22].)
We know that $G$ is an irreducible finite
complex reflexion group.

So it
is one of the groups in the Shephard–Todd list.
The fact that it is generated by reflexions
of order $3$ leaves only a few possibilities.

Let $n$ denote the dimension of its defining
representation, which is $V_\R$,
so that

Since $h\ge q\ge 0$ it follows that
$n\ge h+4\ge 4$. Say that $G=ST_N$, the group
(or family of groups) numbered $N$ in the list of [22]
and consider the table on p. 412 of [3],
which covers the cases $N\in [24, 34]$.
Taking into account the facts that $G$ is generated
by reflexions of order $3$ and that $n\ge 4$ shows that,
if $N\in [24, 34]$, then
$N=32$ and $n=4$, so that $h=0$
and then $q=0$.
For $N\le 23$ look at the table on p.
$301$ of [22]; since $n\ge 4$ we have
$N=1$ or $2$. However, each group in either of these families
admits a surjection onto a non-trivial symmetric group,
so is not generated by elements of order $3$.
If $N\ge 35$ then $G$ is a Weyl group of type $E$,
which groups are not generated by elements of order $3$.

When $h= q =0$
$X$ is the blow-up of a del Pezzo
surface $S$ of degree $1$ at the base point of
$\vert -K_S\vert$. This shows that the
case where $G=ST_{32}$ does occur, and echoes the existence
of an embedding $W(L_4)\inj W(E_8)$.

We continue with a fixed generic curve $C$ of genus $q\ge 2$
and a
generic line bundle $L$ on
it of degree $h+1-q\ge 1$ and consider the Eisenstein surfaces $X_6$
defined by
these data. For a Jacobian elliptic surface $Y$
we denote by ${\HS}(Y)$ the $\Z$-Hodge structure on
$H^2_{prim}(Y,\Z)$. The negative of the cup product defines
a polarization on this; we call it the standard polarization.

Suppose that $f:X_6\to C$ is a
very general Eisenstein surface and that the assumption
(<ref>) holds. Then the natural
homomorphism $\phi$ from $\Aut(X_6)$
to the automorphism group $\Aut(\HS(X_6))$
of the polarized
$\Z$-Hodge structure $\HS(X_6)$
is an isomorphism.
Suppose that $1\ne \g\in\ker\phi$. Then
$\g$ acts trivially on $\vert K_{X_6}\vert$.
Since $K_{X_6}\sim f^*(K_C+M)$, the assumption
(<ref>) ensures that $\vert K_{X_6}\vert$
pulls back from a very ample class on $C$,
so that $\g$ acts trivially on $C$ and the geometric
quotient $Y=[X_6/\langle\g\rangle]$ admits a morphism
to $C$ whose generic fibre is the quotient of
the generic fibre of $f$ by $\langle\g\rangle$.
So $Y$ is birationally ruled over $C$, so that
$p_g(Y)=0$. On the other hand
so vanishes,
which is absurd. So $\phi$ is injective.

To prove the surjectivity of $\phi$ we argue as follows.
By [5], Proposition 7.5,
the monodromy group $G$ has a subgroup $G_0$ of finite index
that embeds
as a subgroup of the Mumford–Tate group $MT(X_6)$
of the polarized $\Z$-Hodge structure of a very
general surface $X_6$ in the family of Eisenstein surfaces
defined by $(C,L)$.

* $MT(X_6)$
is a $\Q$-subgroup of $O_b$ but, because of
the existence of the automorphism $\g$,
$MT(X_6)$ is in fact a $\Q$-subgroup of

* The identity connected component $M^0$
of $M$ is contained in $MT(X_6)$
since $M^0$ is contained
in the $\Q$-algebraic subgroup generated by

* So $MT(X_6)$ contains $SU_B$.
Since $MT(X_6)$ contains the scalars,
it equals $U_B$ and its centralizer is $\Q(\zeta_3)$.

If $\theta$ is an automorphism of the polarized
$\Z$-Hodge structure
$\HS(X_6)=V_\Z$ then $\theta$
normalizes the image of the Deligne torus
$\mathbb{S}=R_{\C/\R}\GG_m$ in $GL(V_\R)$ that
defines $\HS(X_6)_\R$. Examination of the Galois module
$\X^*({\mathbb{S}})$ shows that the $\R$-automorphism
group of $\mathbb{S}$ consists of the
four maps

Since the weight of $\HS(X_6)$ is non-zero,
$\theta$ acts trivially on the copy of $\R^*$ in
$\mathbb{S}$ and so its action on $\mathbb{S}$
is either $z\mapsto z$ or $z\mapsto {\overline{z}}$. Since $H^{2,0}\ne 0$
it follows that $\theta$ acts trivially on $\mathbb{S}$.

Let $Z$ denote the connected
component of the fixed locus of $\theta$ in $GL(V)$;
this is a $\Q$-algebraic subgroup of $GL(V)$ and
$Z_\R$ contains $\mathbb{S}$. So $Z$ contains
$MT(X_6)$, so that $\theta$ centralizes $MT(X_6)$ and lies in
$\Q(\zeta_3)$. But
$\theta$ and $\theta^{-1}$ are integral over $\Z$,
since they act on the finite $\Z$-module $\HS(X_6)$, so
that they both lie in $\Z[\zeta_3]$
and then $\theta$ is a power of $\zeta_6$.

(Generic local Torelli) If $X_6$ is a generic Eisenstein surface
and $\vert K_{X_6}\vert$ has no base points then
the coarse period map

$$per:[\sje]\to [\sD/\G]$$

is injective in an analytic of the point corresponding to $X_6$.
It's enough to allow $X_6$ to be very general.

Since $\vert K_{X_6}\vert$ has no base points,
the infinitesimal Torelli theorem holds for $X_6$.
The result follows at once from the theorem.

Really the important point here is the weaker
result that the automorphism group of the polarized Hodge
structure $\HS$ is induced by the automorphism group of the
modulo automorphisms of $\HS$ that act trivially on the period
So very general Eisenstein surfaces happen to behave like hyperelliptic
curves rather than non-hyperelliptic ones.

$\Q$-Hodge structures and generic Torelli
Suppose that $n$ is an integer. If $X,Y$ are Jacobian elliptic
surfaces then
an $n$-isogeny from $\HS(X)$ to $\HS(Y)$ is a $\Z[1/n]$-isomorphism
$\psi:\HS(X)\otimes\Z[1/n]\to \HS(Y)\otimes \Z[1/n]$ of
$\Z[1/n]$-Hodge structures
such that
$n\psi(\HS(X))\subseteq \HS(Y)\subseteq n^{-1}\psi(\HS(X))$
and $\psi$ preserves the standard polarizations
up to a positive rational scalar multiple.
This notion defines a
$\G_n$ on $\sD/\G$ and on $[\sD/\G]$ and then we can consider
the composite

$$per_n=\G_n\circ per:[\sje_{h,q}]\to[\sD/\G]\to [\sD/\G].$$

This is multi-valued; we say that it is very generally
if, for two points $X,Y$ in $[\sje_{h,q}]$ of which one is very
general, we have
$X=Y$ if the finite set $per_n(X)$ has non-empty intersection
with $per_n(Y)$.

If $\HS(Y)$ is isogenous to $\HS(X_6)$ for a
very general Eisenstein surface $X_6$ then the automorphism
group of $\HS(Y)$, with its polarization, is either
$\langle\zeta_6\rangle$ or $\{\pm 1\}$
$\HS(Y)_\Q$ is isomorphic to $\HS(X)_\Q$.
The proof of Theorem <ref> then shows, first, that every
automorphism $\theta$ of $\HS(Y)$ lies in $\Q(\zeta_3)$
and, second, that $\theta$ is a power of $\zeta_6$.
Since $-1$ is always an automorphism of $\HS(Y)$
the lemma follows.

Under the assumptions (<ref>)
the multi-valued map $per_n$ is very generally injective.
Assume otherwise. As recalled in Section
<ref> the IVHS determines the base curve
$C$ and the ramification divisor $Z$ of the classifying
morphism $\Phi:C\to\bsell$, and then for generic
$\Phi$ the pair $(C,Z)$ determines $\Phi$
modulo the action of the automorphism
group $\GG_m$ of $\bsell$. Since the closure of such an
orbit is a Gauss–Eisenstein pencil, a generic point $X$
of $\sje$ determines a Gauss–Eisenstein pencil, the
closure            of the $\GG_m$-orbit through the
point $X$, and any
failure of $per_n$ to be very generally
can be detected on a very general Gauss–Eisenstein pencil.

Suppose that $X_6$ is a very general Eisenstein surface
and that
$\sX\to B \cong \P^1$ is the Gauss–Eisenstein pencil
generated by $X_6$ and some Gauss surface $X_4$. Let
$P\in B$ denote the point corresponding to $X_6$,
$B'$ the normalization of
the image of $B$ in the coarse moduli space $[\sje^{RDP}_{C,L}]$
and $P'\in B'$ the image of $P$. In an analytic neighbourhood
of $P$ the map $B\to B'$ is just the geometric quotient
by the group $\langle\zeta_6\rangle$. (This action
is not effective; the kernel is
$\{\pm 1\}$).

Consider the multi-valued map
$per_n\vert_{B'}:B'\to [\sD/\Gamma]$; by assumption, this is
not very generally injective in the sense defined above.
However, Corollary <ref> and Lemma <ref>
combine to show that
$per_n\vert_{B'}$ is an isomorphism onto each of its
images $Y$

* in an analytic of $P'$ in $B'$ (when
$\Aut(\HS(Y))=\langle\zeta_6\rangle$) or

* in an analytic of $P$ in $B$ (when $\Aut(\HS(Y))=\{\pm 1\}$).

Since $B'$ is complete there is,
therefore, another point $Q'\in B'$
such that $Q'\ne P'$ and $per_n(P')$ meets $per_n(Q')$.
Let $Q$ be a pre-image of $Q'$ in $B$.
Varying the pencil $B$ by
keeping the Eisenstein
surface $X_6$ fixed and varying the Gauss
surface $X_4$
then gives
a locus $\sL$ in $\sje^{RDP}_{C,L}$,
swept out by the points $Q$,
that consists of
elliptic surfaces whose Hodge structure
is $n$-isogenous to that of $X_6$.
Since a general member of $\sje$ determines
the Gauss–Eisenstein pencil on which it lies,
the point $Q$ varies when $X_4$ varies,
so that $\dim\sL$ is strictly positive.
this contradicts the infinitesimal Torelli theorem.

If $8h>10(q-1)$, $h\ge q+3$ and $q\ge 2$
then a very general surface in $\sje_{h,q}$ is
determined by its polarized $\Q$-Hodge structure.

[3]
A.M. Cohen, Finite complex reflection groups,
Ann. Sci. ENS 9 (1976), 379–436.

[5]
P. Deligne, La conjecture de Weil pour les surfaces $K3$,
Invent Math. 15 (1972), 206–226.

[6]
, La conjecture de Weil II,
Publ. Math. IHÉS 52 (1980), 137–252.

[7]
R. Miranda, The  basic theory of elliptic surfaces,
Pisa, 1989.

[8]
P. Deligne and N. Katz, Séminaire de
Géométrie Algébrique 7 II.

[22]
G.C. Shephard and J.A. Todd, Finite unitary reflection
Canad. J. Math. 6 (1954), 274–304.

[23]
N.I. Shepherd-Barron, Generic Torelli and local Schottky
theorems for Jacobian
elliptic surfaces, Comp. Math., 159 (2023), 2521–2550.

\end

\end