# Two-Stream Consensus Network: Submission to HACS Challenge 2021 Weakly-
Supervised Learning Track

Yuanhao Zhai1,2 Le Wang1 David Doermann2 Junsong Yuan2
1Xi’an Jiaotong University
1State University of New York at Buffalo
<EMAIL_ADDRESS>
###### Abstract

This technical report presents our solution to the HACS Temporal Action
Localization Challenge 2021, Weakly-Supervised Learning Track. The goal of
weakly-supervised temporal action localization is to temporally locate and
classify action of interest in untrimmed videos given only video-level labels.
We adopt the two-stream consensus network (TSCN) [5] as the main framework in
this challenge. The TSCN consists of a two-stream base model training
procedure and a pseudo ground truth learning procedure. The base model
training encourages the model to predict reliable predictions based on single
modality (, RGB or optical flow), based on the fusion of which a pseudo ground
truth is generated and in turn used as supervision to train the base models.
On the HACS v1.1.1 dataset, without fine-tuning the feature-extraction I3D
models, our method achieves $22.20\%$ on the validation set and $21.68\%$ on
the testing set in terms of average mAP. Our solution ranked the 2nd in this
challenge, and we hope our method can serve as a baseline for future academic
research.

##  1 Our Solution

We adopt the two-stream consensus network (TSCN) [5] as the main framework. It
consists of two main procedures: two-stream base model training and pseudo
ground truth learning. Figure 1 shows the framework of our method.

###  1.1 Feature Extraction

We construct our model upon snippet-level feature sequences extracted from the
raw video volume. The RGB and optical flow features are extracted with pre-
trained I3D [1]) from non-overlapping fixed-length RGB frame snippets and
optical flow snippets, respectively. Formally, given a video with $T$ non-
overlapping snippets, we denote the RGB features and optical flow features as
$\\{\mathbf{f}_{\text{RGB},i}\\}_{i=1}^{T}$ and
$\\{\mathbf{f}_{\text{flow},i}\\}_{i=1}^{T}$, respectively, where
$\mathbf{f}_{\text{RGB},i},\mathbf{f}_{\text{flow},i}\in\mathbb{R}^{D}$ are
the feature representations of the $i$-th RGB frame and optical flow snippet,
respectively, and $D$ represents the channel dimension.

Figure 1: An overview of the Two-Stream Consensus Network, which consists of
three parts: (1) feature extraction, where RGB and optical flow snippet-level
features are pre-extracted; (2) two-stream base models, where action
recognition is performed on the two modalities with two-stream base models,
respectively; (3) pseudo ground truth generation, where a frame-level pseudo
ground truth is generated from the two-stream late-fusion attention sequence
and in turn provides frame-level supervision to two-stream base models.

###  1.2 Two-Stream Base Models

After obtaining the RGB and optical flow features, we first use two-stream
base models to perform the video-level action classification. The features of
two modalities are fed into two separate base models, respectively, and the
two base models use the same architecture but do not share parameters.
Therefore, we omit the subscript RGB and flow to denote a general operation
for both modalities.

To embed the extracted features to task-specific space, we use a single
temporal convolutional layer with a kernel size $3$ to embed the input
feature, and generate a set of new features $\\{\mathbf{x}_{i}\\}_{i=1}^{T}$,
where $\mathbf{x}_{i}\in\mathbb{R}^{D}$.

As a video may contain background snippets, to perform video-level
classification, we need to select snippets that are likely to contain action
instances and meanwhile filter out snippets that are likely to contain
background. To this end, an attention value $a_{i}\in(0,1)$ to measure the
likelihood of the $i$-th snippet containing an action is given by a fully-
connected (FC) sigmoid layer. We then perform attention-weighted pooling over
the feature sequence to generate a single foreground feature
$\mathbf{x}_{\text{fg}}$, and feed it to an FC softmax layer to get the video-
level prediction:

$\mathbf{x}_{\text{fg}}=\frac{1}{\sum_{i=1}^{T}a_{i}}\sum_{i=1}^{T}a_{i}\mathbf{x}_{i},$
(1)
$\hat{y}_{c}=\frac{e^{\mathbf{w}_{c}\cdot\mathbf{x}_{\text{fg}}+b_{c}}}{\sum_{i=1}^{C}e^{\mathbf{w}_{i}\cdot\mathbf{x}_{\text{fg}}+b_{i}}},$
(2)

where $\hat{y}_{c}$ is the probability that the video contains the $c$-th
action, and $\mathbf{w}_{c}$ and $b_{c}$ are the weight and bias of the FC
layer for category $c$, respectively. The classification loss function
$\mathcal{L}_{\text{cls}}$ is defined as the standard binary cross entropy
loss.

In addition, the temporal-class activation map (T-CAM)
$\\{\textbf{s}_{i}\\}_{i=1}^{T}$, $\textbf{s}_{i}\in\mathbb{R}^{C}$ is also
generated by sliding the classification FC softmax layer over all snippet
features:

$s_{i,c}=\frac{e^{\mathbf{w}_{c}\cdot\mathbf{x}_{i}+b_{c}}}{\sum_{j=1}^{C}e^{\mathbf{w}_{j}\cdot\mathbf{x}_{i}+b_{j}}},$
(3)

where $s_{i,c}$ is the T-CAM value of $i$-th snippet for category $c$.

For better attention and T-CAM learning, we further adopt a smooth loss, the
attention normalization loss [5], a distinctness loss, and a variant of the
self-guided attention loss [2] in the base model training.

The smooth loss enforces temporally proximate snippets to give similar
attention predictions, and thus helps generate a more smooth attention
sequence:

$\mathcal{L}_{\text{smooth}}=\frac{1}{T-1}\sum_{t=1}^{T-1}|a_{t}-a_{t+1}|$ (4)

The attention normalization loss [5] maximizes the difference between the
average top-$l$ attention values and the average bottom-$l$ attention values,
and forces the foreground attention to be $1$ and background attention to be
$0$:

$\mathcal{L}_{\text{norm}}=\frac{1}{l}\min_{\begin{subarray}{c}a\subset\\{a_{i}\\}\\\
|a|=l\end{subarray}}\sum_{\phi\in
a}\phi-\frac{1}{l}\max_{\begin{subarray}{c}a\subset\\{ai\\}\\\
|a|=l\end{subarray}}\sum_{\phi\in a}\phi,$ (5)

where $l=\max\left(1,\lfloor\frac{T}{k}\rfloor\right)$ and $k$ is a
hyperparameter to control the selected snippets.

The distinctness loss $\mathcal{L}_{\text{dist}}$ encourages the foreground
feature $\mathbf{x}_{\text{fg}}$ and background feature
$\mathbf{x}_{\text{bg}}$ to be distinct in the feature space:

$\mathcal{L}_{\text{dist}}=\max\left(0,\frac{\mathbf{x}_{\text{fg}}\cdot\mathbf{x}_{\text{bg}}}{\|\mathbf{x}_{\text{fg}}\|\|\mathbf{x}_{\text{bg}}\|}-m\right),$
(6)

where $\|\cdot\|$ is the L2 norm, and $m$ is a hyperparameter empirically set
to $0.5$.

The self-guided attention loss [2] pursues a consensus between the bottom-up
attention and the top-down T-CAM. In our method, as we do not exploit the
background classification, we discard the background modeling term in the
original guide loss. Besides, we empirically observe that the attention tends
to produce more reliable activations than the T-CAM, and thus we detach the
gradient for the attention in the guide loss. The guide loss variant employed
in our method is formulated as:

$\mathcal{L}_{\text{guide}}=\frac{1}{T}\sum_{i=1}^{T}|\text{sg}(a_{i})-s_{i,c^{*}}|,$
(7)

where $\text{sg}(\cdot)$ denotes stop gradient, and $c^{*}$ is the ground
truth action class111If there are multiple classes contained in the video, we
max-pool the T-CAM across all ground truth classes..

The overall loss for the base model training is a weighted sum of the loss
terms:

$\mathcal{L}_{\text{base}}=\mathcal{L}_{\text{cls}}+\lambda_{1}\mathcal{L}_{\text{smooth}}+\lambda_{2}\mathcal{L}_{\text{norm}}+\lambda_{3}\mathcal{L}_{\text{dist}}+\lambda_{4}\mathcal{L}_{\text{guide}},$
(8)

where $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$ and $\lambda_{4}$ are weight
parameters.

###  1.3 Pseudo Ground Truth Learning

We iteratively refine the two-stream base models with a frame-level pseudo
ground truth, which is generated by two-stream prediction fusion.
Specifically, we divide the whole training process into several refinement
iterations. At refinement iteration $0$, only video-level labels are used for
training. And at refinement iteration $n+1$, a frame-level pseudo ground truth
is generated at refinement iteration $n$, and provides frame-level supervision
for the current refinement iteration.

Speficially, we use the fusion attention sequence
$\\{a_{\text{fuse},i}^{(n)}\\}_{i=1}^{T}$ at refinement iteration $n$ to
generate pseudo ground truth $\\{\mathcal{G}_{i}^{(n+1)}\\}_{i=1}^{T}$ for
refinement iteration $n+1$, where $a_{\text{fuse},i}^{(n)}=\beta
a_{\text{RGB},i}^{(n)}+(1-\beta)a_{\text{flow},i}^{(n)}$, and $\beta\in[0,1]$
is a hyperparameter to control the relative importance of RGB and flow
attentions.

The pseudo ground truth thresholds the attention sequence to generate a binary
sequence:

$\mathcal{G}_{i}^{(n+1)}=\left\\{\begin{array}[]{lr}1,\quad
a_{\text{fuse},i}^{(n)}>\theta;&\\\ 0,\quad
a_{\text{fuse},i}^{(n)}\leq\theta,&\\\ \end{array}\right.$ (9)

where $\theta$ is the threshold value.

After obtaining the frame-level pseudo ground truth, we force the attention
sequence generated by each stream to be similar to the pseudo ground truth
with a binary cross entropy loss:

$\displaystyle\mathcal{L}_{\text{pseudo}}^{(n+1)}=$
$\displaystyle-\frac{1}{T}\sum_{i=1}^{T}\mathcal{G}_{i}^{(n+1)}\log\left(a_{i}^{(n+1)}\right)+$
(10)
$\displaystyle\left(1-\mathcal{G}_{i}^{(n+1)}\right)\log\left(1-a_{i}^{(n+1)}\right)$

At refinement iteration $n+1$, the total loss for each stream is

$\mathcal{L}_{\text{total}}^{(n+1)}=\mathcal{L}_{\text{cls}}+\lambda_{3}\mathcal{L}_{\text{dist}}+\lambda_{4}\mathcal{L}_{\text{guide}},+\lambda_{5}\mathcal{L}_{\text{pseudo}}^{(n+1)},$
(11)

where $\lambda_{5}$ is a hyperparameter to control the relative importance of
two losses. Note that we remove the attention normalization loss and in the
pseudo ground truth learning, as the loss term assumes at least $\frac{1}{k}$
and $\frac{1}{k}$ of each video are actions and backgrounds, respectively.
However, it does not always hold (some videos do not contain background), and
will bring noise for the pseudo ground truth learning. The smooth loss is also
removed as it leads to trivial solution where all videos are actions without
the supervision the attention normalization loss.

###  1.4 Action Localization

During testing, we first temporally upsample the attention sequence and T-CAM
by a factor of $8$ via linear interpolation. Then, we select top-$2$ action
categories from the fusion video-level prediction
$\hat{\textbf{y}}_{\text{fuse}}$ to perform action localization, where
$\hat{\textbf{y}}_{\text{fuse}}=\beta\hat{\textbf{y}}_{\text{RGB}}+(1-\beta)\hat{\textbf{y}}_{\text{flow}}$.
Action proposals are generated by progressively thresholding the attention
sequence from $0$ to $1.0$, with a step size of $0.025$, and concatenating
proximate snippets. The action proposals are scored following TSCN [5].
Formally, given action proposal $(t_{s},t_{e},c)$, fusion attention
$\\{a_{\text{fuse},i}\\}_{i=1}^{T}$ and T-CAM
$\\{\textbf{s}_{\text{fuse},i}\\}_{i=1}^{T}$, where
$\textbf{s}_{\text{fuse},i}=\beta\textbf{s}_{\text{RGB},i}+(1-\beta)\textbf{s}_{\text{flow},i}$,
the score $\psi$ is computed as

$\displaystyle\psi=$
$\displaystyle\frac{\sum_{i=t_{s}}^{t_{e}}a_{\text{fuse},i}s_{\text{fuse},i,c}}{t_{e}-t_{s}}-$
(12)
$\displaystyle\frac{\sum_{i=T_{s}}^{T_{e}}a_{\text{fuse},i}s_{\text{fuse},i,c}-\sum_{i=t_{s}}^{t_{e}}a_{\text{fuse},i}s_{\text{fuse},i,c}}{T_{e}-T_{s}-(t_{e}-t_{s})},$

where $T_{s}=t_{s}-\frac{L}{4}$, $T_{e}=t_{e}+\frac{L}{4}$, and
$L=t_{e}-t_{s}$. We finally use NMS with IoU threshold $0.6$ to filter out
redundant detections.

##  2 Experiments and Discussions

###  2.1 Implementation Details

The optical flow is estimated via the TV-L1 algorithm [4]. The feature-
extraction backbone I3D [1] is pre-trained on the Kinetics dataset [1], and is
_not_ fine-tuned on the HACS dataset [6]. In this competition, we use the off-
the-shelf $2$ FPS RGB snippet-level features provided by the dataset [6], and
extract the optical flow features with a snippet length of $16$ frames. The
majority of the hyperparameters are set according to [2, 5]:
$\lambda_{1}=\lambda_{2}=\lambda_{4}=0.1$, $k=8$, and $\theta=0.5$. Other
hyperparameters are set according to a grid search: $\beta=0.6$,
$\lambda_{3}=0.1$ and $\lambda_{5}=0.01$. We use the AdamW optimizer with a
fixed learning rate $0.0005$. We train the model for a total of $5$ refinement
iterations, with each refinement iteration contains $10$ epochs. At each
refinement iteration, we simply select the latest model from the last
refinement iteration to generate the pseudo ground truth.

Table 1: Single-stream performance with different loss combinations on the
HACS validation set.

$\mathcal{L}_{\text{cls}}$ | $\mathcal{L}_{\text{smooth}}$ | $\mathcal{L}_{\text{norm}}$ | $\mathcal{L}_{\text{dist}}$ | $\mathcal{L}_{\text{guide}}$ | mAP@IoU (%)
---|---|---|---|---|---
0.5 | 0.75 | 0.95 | Avg
✓ | - | - | - | - | 9.23 | 4.45 | 1.12 | 5.03
✓ | ✓ | - | - | - | 17.53 | 11.41 | 4.54 | 11.69
✓ | ✓ | ✓ | - | - | 25.82 | 15.77 | 5.42 | 16.33
✓ | ✓ | ✓ | ✓ | - | 26.54 | 16.18 | 5.50 | 16.86
✓ | ✓ | ✓ | ✓ | ✓ | 27.46 | 17.19 | 6.26 | 17.69
(a) RGB stream-only localization performance.

$\mathcal{L}_{\text{cls}}$ | $\mathcal{L}_{\text{smooth}}$ | $\mathcal{L}_{\text{norm}}$ | $\mathcal{L}_{\text{dist}}$ | $\mathcal{L}_{\text{guide}}$ | mAP@IoU (%)
---|---|---|---|---|---
0.5 | 0.75 | 0.95 | Avg
✓ | - | - | - | - | 5.60 | 2.17 | 0.19 | 2.63
✓ | ✓ | - | - | - | 14.47 | 9.43 | 3.40 | 9.64
✓ | ✓ | ✓ | - | - | 19.08 | 11.73 | 4.75 | 12.31
✓ | ✓ | ✓ | ✓ | - | 19.24 | 11.84 | 4.83 | 12.40
✓ | ✓ | ✓ | ✓ | ✓ | 19.57 | 12.17 | 4.90 | 12.74
(b) Flow stream-only localization performance.

Table 2: Performance w/ pseudo ground truth learning in different refinement iterations on the HACS validation and testing sets. | Modality | Validation | Test
---|---|---|---
| 0.5 | 0.75 | 0.95 | Avg | Avg
0 | RGB | 27.46 | 17.19 | 6.26 | 17.69 | -
Flow | 19.57 | 12.17 | 4.90 | 12.74 | -
Fusion | 29.91 | 18.50 | 6.99 | 19.12 | 18.75
1 | RGB | 26.85 | 16.98 | 6.27 | 17.38 | -
Flow | 23.57 | 13.86 | 5.27 | 14.74 | -
Fusion | 31.30 | 19.14 | 6.96 | 19.83 | -
2 | RGB | 30.45 | 18.42 | 6.39 | 19.16 | -
Flow | 24.09 | 14.39 | 5.43 | 15.16 | -
Fusion | 33.47 | 20.03 | 6.81 | 20.91 | 20.30
3 | RGB | 32.62 | 19.32 | 6.36 | 20.18 | -
Flow | 23.21 | 13.97 | 4.82 | 14.58 | -
Fusion | 35.07 | 20.85 | 6.87 | 21.82 | -
4 | RGB | 33.54 | 19.57 | 6.17 | 20.54 | -
Flow | 23.12 | 13.74 | 4.50 | 14.38 | -
Fusion | 35.43 | 20.94 | 6.80 | 21.93 | 21.33

###  2.2 Results

Two-stream base models. The performance of two-stream base models w/o pseudo
ground truth supervision is reported in Table 1, where different combinations
of loss terms are evaluated. The results show the addition of each loss
contributes to the performance improvement.

Pseudo ground truth learning. Table 2 reports the performance changes in
different refinement iterations. The results reveal that pseudo ground truth
consistently improves the fusion results, and eventually saturates at the
$3$-rd and $4$-th refinement iterations. The pseudo ground truth also greatly
improves the single-stream models. Specifically, it improves the performance
of the RGB model from $17.69\%$ to $20.54\%$ in terms of average mAP, and
improves the performance of the flow model from $12.74\%$ to $15.16\%$.

Exponential moving average emsemble. Inspired by the mean teacher [3], after
the pseudo ground truth learning, we ensemble the models from all $5$
refinement iterations by exponentially moving average their parameters with a
successive weight $0.2$. The final ensemble model achieves $22.20\%$ average
mAP on the HACS validation set, and $21.68\%$ on the HACS testing set.

## Acknowledgements

This work is supported in part by the Defense Advanced Research Projects
Agency (DARPA) under Contract No. HR001120C0124. Any opinions, findings and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the Defense Advanced
Research Projects Agency (DARPA).

## References

  * [1] Joao Carreira and Andrew Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In CVPR, pages 6299–6308, 2017.
  * [2] Phuc Xuan Nguyen, Deva Ramanan, and Charless C Fowlkes.  Weakly-supervised action localization with background modeling.  In ICCV, pages 5502–5511, 2019.
  * [3] Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  arXiv preprint arXiv:1703.01780, 2017.
  * [4] Christopher Zach, Thomas Pock, and Horst Bischof.  A duality based approach for realtime tv-l 1 optical flow.  In PR, pages 214–223, 2007.
  * [5] Yuanhao Zhai, Le Wang, Wei Tang, Qilin Zhang, Junsong Yuan, and Gang Hua.  Two-stream consensus network for weakly-supervised temporal action localization.  In ECCV, pages 37–54, 2020.
  * [6] Hang Zhao, Antonio Torralba, Lorenzo Torresani, and Zhicheng Yan.  Hacs: Human action clips and segments dataset for recognition and temporal localization.  In ICCV, pages 8668–8678, 2019.


One of the most promising attempts towards solving optimization problems with quantum computers in the noisy intermediate scale era of quantum computing are variational quantum algorithms.
The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, combinatorial optimization problems.
As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit, thereby limiting the search to the much smaller Hilbert space of feasible solutions.
In this work we develop mixing operators for a wide range of scheduling problems including the flexible job shop problem.
These mixing operators are based on a special control scheme defined by a constraint graph model.
After describing an explicit construction of those mixing operators, they are proven to be feasibility preserving, as well as exploring the feasible subspace.

§.§.§ Keywords:

Quantum Computing, Quantum Algorithms, Constraint-Mixer QAOA, Job-Shop Scheduling

§ INTRODUCTION

The usage of quantum mechanical phenomena in computing provably enables asymptotic speedups over classical computers in some computational tasks (<cit.>, <cit.>), and researchers are aiming to discover such algorithmic breakthroughs in others.
The reality of quantum computing right now, sometimes called the noisy intermediate scale quantum (NISQ) era, presents additional challenges: While quantum processors are only available with a modest number of noisy qubits, the algorithms under consideration must address these shortcomings. In the case of quantum optimization, hopes for near- to mid-term algorithmic advances rest on the shoulders of variational hybrid algorithms (<cit.>).
All of them involve a parameterized quantum circuit $U(\theta)$ which is used to generate an ansatz state

\begin{equation}
\ket{\psi(\theta)} := U(\theta)\ket{0}.
\end{equation}

Measuring this ansatz state several times in the computational basis provides solution candidates (the bit string representations of the computational basis states) to the (binary) optimization problem. Based on the quality of these samples with respect to the optimization problem, the parameters $\theta$ are then updated and fed back into the quantum circuit.
In this algorithmic scheme, one qubit roughly corresponds to one binary variable in the optimization problem. Without the need for spatial overhead, such as auxiliary quantum registers, relevant problem sizes can be targeted much sooner, thereby adressing the “intermediate scale" concern.
Due to the variational nature of the algorithm, where measurement outcomes inform the choice of parameters and thus the eventual solution, noise is taken into account and filtered out to a certain extent. This is in contrast to pure quantum algorithms, where each step “trusts" the preceding steps to prepare a certain quantum state, thus allowing errors to propagate easily.

The Quantum Alternating Operator Ansatz hadfield_diss also referred to as the constraint mixer Quantum Approximate Optimization Algorithm () CM_QAOA_Fuchs2022 is a framework for such algorithms. Its setup is very similar to the better known Quantum Approximate Optimization Algorithm farhi_qaoa, involving alternating mixing and phase separation layers.
The main distinction point of  is to explore only feasible solutions for a given optimization problem, thus drastically reducing the dimension of the search space. This is in contrast to many other variational algorithms like standard QAOA, where infeasible solutions are assigned undesirably high values via penalty terms and the mixing layers create a superposition of all bit strings.
In this work, we introduce a concrete construction following this scheme, which is suitable for a possibly wide range of scheduling problems including the Flexible Job-Shop Problem ().
To this end we consider a constraint-graph model that encodes the constraints of -instances in a graph, similarly to the work of <cit.>.
We use the constraint graph to define a unitary mixing operator for the  which is made up of controlled permutation operators.
We prove that this mixing operator is both feasibility preserving and explores the feasible subspace.

In <Ref> we formally introduce the two main ingredients of this work, namely the algorithmic framework CM-QAOA in <Ref> and the flexible job shop problem in <Ref>. Section <ref> goes on to construct the constraint graph of the  (<Ref>). In <Ref> we go on to introduce the concept of controlled permutation unitaries and provide an explicit construction of a mixing operator for the . We prove that this operator is feasibility-preserving in <Ref> and that it explores the feasible subspace in <Ref>.
Finally, in <Ref>, the results are compared to related work and the practical limitations of our approach are discussed.

§ PRELIMINARIES

§.§ The Quantum Alternating Operator Ansatz

The , originally proposed by hadfield_diss, is a framework of variational quantum algorithms generalizing the Quantum Approximate Optimization Algorithm farhi_qaoa.
The  allows for a restriction of the search space to the subspace of feasible states, i.e. computational basis states whose bit string representations correspond to feasible solutions to an optimization problem. More precisely, the subspace of feasible solutions is spanned by computational basis states corresponding to bit strings which satisfy all constraints of the given problem instance.
This potentially decreases the size of the state space in which the goal function is to be optimized substantially.
To achieve this, the main effort in algorithm design is shifted from constructing a cost Hamiltonian representing the goal function as well as the constraints of a problem instance towards the implementation of the constraints directly into mixing operators. A combinatorial optimization problem which can be solved by  is given by a pair $\of{F,f}$, where, for $N\in\N$, $f:\cof{0,1}^N\to \R$ is a cost function to be minimized[As maximization of $f$ is the same as minimization of $-f$, it is sufficient to only consider minimization problems.] and

\begin{equation}\label{eq:feas_classical}
F\subset \cof{0,1}^N
\end{equation}

is the set of feasible solutions typically characterized by a list of constraints. In the  the choice of alternating operators is more flexible compared to the QAOA. Especially, the mixing operators no longer need to be generated by a mixer Hamiltonian as in the work of <cit.>, but is rather required to fulfill certain design criteria <cit.>. The substitute for the QAOA-mixer $\sum_i X_i$ must have two features which ensure that the search of  remains within the feasible subspace $\feas$ and at the same time every feasible state can be reached for a suitable choice of parameters.

Let the tuple $(F \subset \{0,1\}^N, f)$ define a constrained optimization problem and let $B_{\beta} = \set*{\mix\of{\beta}|\beta\in\R}$ be a family of unitaries acting on the Hilbert space $\mathcal{H} \coloneqq (\C^2)^{\otimes N}$. Denote the subspace of feasible solutions by $\feas \coloneqq \Span(\{\ket{x} | x \in F\}) \subset \mathcal{H}$.
The family $B_\beta$ is said to …

… preserve feasibility, if and only if

… explore the feasible subspace, if and only if for all $x,y\in F\colon$ there exists a $\beta^{\ast}\in\R\qc$ and $r\in\N$ s.t.

\bra{y}\mix^r\of{\beta^\ast}\ket{x}

A  instance is given by two families of unitary operators, $B_{\beta} = \set*{\mix\of{\beta} | \beta\in\R}$ and $C_{\gamma} = \set*{e^{-\imun \gamma H_f}|\gamma\in\R}$, and a feasible initial state $\ket{\psi_0}\in\feas$, such that each operator in $B_{\beta}$ fulfills the criteria in <Ref>.
Here $H_f = \sum_{x \in \{0,1\}^N} f(x) \ketbra{x}$ is the Hamiltonian representing the function $f$ diagonally.\\
The operator $(β)$ is referred to as the \emph{mixing operator} and the operator $e^-γH_f$ is called \emph{phase-separation operator}.
\end{definition}

\subsection{The Flexible Job-Shop Problem}\label{subsec:fjsp}
An example of a combinatorial optimization problem, which is relevant to industrial applications, is the \emph{Flexible Job-Shop Problem} (\fjsp{}).
A number of jobs, each of which is given by a sequence of operations of varying processing times, have to be scheduled on a number of machines with the goal of optimizing a performance indicator, e.g. minimizing the overall execution time, often called \emph{makespan}.
More concretely, an instance of \fjsp{} comprises the following data:
\begin{itemize}
\item $n_J$ jobs $J_i\in J=\cof{J_1,\dots,J_{n_J}}$, for some $n_J\in \N$,
\item For each $j\in [n_J]$, a set of $p_j$ operations $O_{j,o}$ in $O_j=\cof{O_{j,1},\dots,O_{j,p_j}}$, for some $p_j\in \N$
\item $n_M$ machines $M_m$ in $M=\cof{M_1,\dots,M_{n_M}}$, for some $n_M\in\N$,
\item time-slots $T_t$ in $T=\cof{T_1,\dots,T_{n_T}}$, for some number of time steps $n_T\in\N$.
\end{itemize}
Each job $J_j$ consists of the operations $O_j$, that shall be assigned to a machine $M_m$ in $M$ at a given time-slot $T_t∈T$.
Denoting the set of all operations by $O = ⋃_j,o O_j,o$, an \emph{assignment} of operation $O_j,o$ is defined to be a tuple $(O_j,o,M_m,T_t)∈O×M×T$.
A subset $S⊆O×M×T$ of assignments, is called a \emph{schedule}.
The following additional data are needed to define feasible schedules.
\begin{itemize}

\item For each $O_{j,o}\in O$ a set $M_{j,o}\subseteq M$ of machines the operation may be executed on.
\item For each $O_{j,o}\in O$ and $M_m\in M$, a duration $d_{j,o,m}\in N$ the operation $O_{j,o}$ takes, when being executed on machine $M_m$.
If $M_m\notin M_{j,o}$ the corresponding duration does not matter and is set to infinity $d_{j,o,m}=\infty$.
\end{itemize}

A schedule is called feasible if it satisfies the following constraints:
\begin{enumerate}
\item\label{itm:ass_constr}\textbf{Assignment constraint} For every operation $O_{j,o}\in O$, there is exactly one time-slot $T_t\in T$ and exactly one machine $M_m\in M$, such that $\of{O_{j,o},M_m,T_t}\in S$. In other words, $\of{O_{j,o},M_m,T_t}\in S \Rightarrow \of{O_{j,o},M_{m'},T_{t'}} \notin S$ if $m \neq m'$ and $t \neq t'$.
\item\label{itm:ord_constraint} \textbf{Order constraint} For all assignments $\of{O_{j,o},M_m,T_t}$, $\of{O_{j,o\primed},M_{m\primed},T_{t\primed}}\in S$ with $o<o\primed$, operation $O_{j,o\primed}$ is started only after operation $O_{j,o}$ has been finished, i.e. $t + d_{j,o,m} \leq t\primed$.
\item \label{itm:mach_constr} \textbf{Machine constraint} For every machine $M_m\in M$, operations $O_{j,o} \neq O_{j\primed,o\primed} \in O$ and $T_t,T_{t\primed} \in T$ with $\of{O_{j,o},M_m,T_t},\of{O_{j\primed,o\primed},M_m,T_{t\primed}} \in S$ we have $t\primed \notin [t,t+d_{j,o,m})$.
That is, at no point in time two operations are being processed simultaneously on the same machine.
\end{enumerate}
A schedule is called \emph{feasible} if each of the constraints is satisfied.
The number of time steps $n_T$ must be chosen such that it is guaranteed that a feasible schedule finishing within $n_T$ steps exists. This is usually achieved by constructing a feasible schedule via some computationally cheap heuristic method.
The aim of the \fjsp{} is to find a feasible schedule, which optimizes a cost function.
Cost functions for the \fjsp{} can be defined in various fashions \parencite{fjsp_review}. One typical choice which will be our choice in this work is the makespan $C(S)max*T_t + d_j,o,m | O_j,o,M_m,T_t∈S$, i.e. the total processing time.
\newline

We formulate the \fjsp{} as a binary combinatorial optimization in the sense of \cref{eq:feas_classical} as follows.
Every possible schedule $S⊆O×M×T$ (feasible or not) can be encoded by some binary string $x=x_1…x_N∈0,1^N$, where $NO×M×T$.
Each $x_i$ denotes whether a given assignment is part of the schedule $S$.
More precisely for a given schedule $S$, set
\begin{equation}
x_i \mDef \begin{cases}
1, & \iota^{-1}(i)\in S\\
0, & \text{else},
\end{cases}
\end{equation}
where $ι  O×M×T →1,…, N$ is a bijective map, enumerating all possible assignments.
Thus $ι$ induces a bijection $I 𝒫O×M×T →0,1^N$.
The set $F⊆0,1^N$ of feasible binary strings is then the set of binary strings $x∈0,1^N$,
such that $Sx I^-1x$ is a feasible schedule.
Together with the cost function $f(x)Cι^-1(x)$, $(F,f)$ is a binary combinatorial optimization problem as above.
In particular, the bit $x_ι(O_o,M_m,T_t)$ is set to 1 if we assign operation $o$ to machine $m$ at time $t$.

\section{Graph-based Constraint Mixer Operators}\label{sec:cm-operators}
Many scheduling problems may be formulated as some variation of a graph-coloring problem \parencite{Marx2004GRAPHCP}.
The common idea in all such approaches is to consider a graph, where each vertex corresponds to one object (job, assignment of a job to a machine,\dots), and the set of edges is constructed such that ``conflicting" objects share an edge.
Roughly speaking, the solution of the scheduling problem then becomes equivalent to finding some coloring of the corresponding graph \parencite{Marx2004GRAPHCP}.
In many cases, each color represents a time slot or machine for the object to be assigned to.
However, this approach is hard to realize for the \fjsp{}, because the available assignments for each job depend on the assignments of all the operations.
Nevertheless, the \fjsp{} can be translated to a constraint graph:
In contrast to other scheduling problems, not each job but each possible assignment $(j,o,m,t)$ corresponds to a vertex of the graph.
Then each pair of vertices, whose corresponding assignments are in conflict with each other, are connected by an edge.
The resulting graph $G=(V,E)$ now encodes all the constraints of a given \fjsp{} instance.
Further, each feasible schedule corresponds to a selection $S⊆V$ of $S=k$ vertices, such that no pair of vertices in $S$ share an edge, i.e $(j,k) ∈S^2 ⇒(j,k) ∉E$.

\subsection{The Constraint Graph of \fjsp{}}\label{subsec:fjsp-constraint-graph}
\begin{figure*}
\centering
\input{Figures/fjsp.tikz}
\caption{A visualization of an example constraint-graph for the \fjsp{}.
Here the instance is given by $J=\{J_1,J_2\}$, $O=\{O_{1,1},O_{1,2},O_{2,1}\}$, $M=\{M_1, M_2\}$, $M_{1,1}=M_{1,2}=M$, $M_{2,1}=\{M_2\}$ and $d_{j,o,m} = 1$ for all $j$, $o$, $m$.
The nodes are labeled as $i$, $m$, $t$, where $i=1$ denotes $O_{1,1}$, $i=2$ denote $O_{1,2}$ and $i=3$ denotes $O_{2,1}$.
Due to the assignment constraint, each operation corresponds to a complete subgraph, where the edges are drawn solid.
The rest of the edges, corresponding to other constraints, are drawn dashed.
The nodes highlighted in grey correspond to a feasible solution of this \fjsp{} instance.
Note that no marked nodes are connected with an edge.
\label{fig:fjsp_graph}
\end{figure*}
Consider a \fjsp{} instance, characterized by the data listed in \Cref{subsec:fjsp}. Denote the set of assignments by $𝒜 O ×M ×T$.
Note that the constraints \ref{itm:ass_constr}, \ref{itm:ord_constraint} and \ref{itm:mach_constr} are all formulated in terms of pairs of assignments.
We denote these sets of conflicting pairs with respect to assignment, order and machine constraints by

\begin{align}
\Omega^{(A)} &= \set*{
a,a' \in \mathcal{A}|
a,a' \text{ are in conflict with \ref{itm:ass_constr}}
},   \\
\Omega^{(O)} &= \set*{
a,a' \in \mathcal{A}|
a,a' \text{ are in conflict with \ref{itm:ord_constraint}}
},   \\
\Omega^{(M)} &= \set*{
a,a' \in \mathcal{A}|
a,a' \text{ are in conflict with \ref{itm:mach_constr}}
\end{align}

%For a precise definition of the constraint graph for an \fjsp-instance given by $J$, ${O = \bigcup_{J_j\in J} O_j}$, $M$, $\set*{M_{j,o} | O_{j,o}~\in~O}$ and $\set*{d_{j,o,m}|O_{j,o}~\in~O,\,~M_m~\in~M}$ define the following three sets ${\Omega^{(A)} \coloneqq \bigcup_{O_{j,o} \in O} \Omega^{(A)}_{j,o}} $, ${\Omega^{(O)}\coloneqq \bigcup_{J_j\in J}\Omega^{(O)}_j} $, and $ {\Omega^{(M)}=\bigcup_{M_m\in M}\Omega^{(M)}_m}$, of assignment combinations in conflict with the assignment constraint ($\Omega^{(A)}$), order constraint ($\Omega^{(O)}$) or machine constraint ($\Omega^{(M)}$), where
%    \Omega^{(A)}_{j,o} &= \set*{
%    \left(\of{O_{j,o}, M_m, T_t},\of{O_{j,o}, M_{m\primed}, %T_{t\primed}}\right)|
%        m\neq m\primed \lor t\neq t\primed
%    }   \\
%    \Omega^{(O)}_j &= \set*{
%    \left(\of{O_{j,o}, M_{m}, T_{t}},\of{O_{j,o\primed}, M_{m\primed}, T_{t\primed}}\right) |
%        o<o\primed \colon\: t+d_{j,o,m}> t\primed
%    }   \\
%    \Omega^{(M)}_m &= \set*{
%    \left(\of{O_{j,o}, M_{m}, T_{t}},\of{O_{j\primed,o\primed}, M_{m}, T_{t\primed}}\right) |
%    t\leq t\primed < t+d_{j,o,m}
%    },
%for $O_{j,o}\in O$, $J_j\in J$ and $M_m\in M$.
Then the construction of the constraint graph described above results in $G=(V, E)$ with
\begin{align}
V &= \set*{\iota\big(O_{j,o},M_m,T_t\big)\in  [N]  | M_m \in M_{j,o}}\,,     \\
E &= \set*{(j,k) | \cof{\iota^{-1}(j),\iota^{-1}(k)} \in \Omega^{(\text{total})}}\,,
\end{align}
where $Ω^(total) Ω^(A) ∪Ω^(O)∪Ω^(M)$  and $ι$ is the bijective enumeration of the set of all schedules.
The number $k$ of vertices to be colored is the total number of operations $k=O$.
\Cref{fig:fjsp_graph} shows the constraint graph for a small instance of the \fjsp{} together with a feasible solution.

\subsection{Graph-controlled Permutation Mixers}\label{subsec:graph-controlled permuation mixers}%
In the following, we construct mixing operators for the CM-QAOA for the flexible job shop problem making use of the constraint graph formalism. More concretely, an $N$-bit string $x ∈{0,1}^N$ encoding a schedule $S$ is equivalent to marking $x$ vertices of the $N$-vertex constraint graph, where $x = ∑_jx_j$ is the \emph{Hamming weight} of $x$. The validity of the bit string $x$ corresponds to the property that

\begin{itemize}
\item there are no adjacent marked vertices in $G$:
\begin{equation}\label{eq:adjacent_nodes}
(j,k)\in E \imply \lnot(x_j \land x_k)
\end{equation}
\item exactly $k$ vertices are marked:
\begin{equation}\label{eq:hamming_weight}
\abs{x} = k.
\end{equation}
\end{itemize}

Define the set $F$ of feasible solutions satisfying these constraints as
\begin{equation}
F = \set*{x\in\cof{0,1}^N | x\text{ satisfies \cref{eq:adjacent_nodes} and \cref{eq:hamming_weight}}}
\label{eq:graph_constraints}
\end{equation}
Consider a quantum register of $N$ qubits in $(^2)^⊗N$ and denote its computational basis by $*|x⟩ | x∈0,1^N$. We define the \emph{feasible subspace} to be $ℱ = _*|x⟩ | x∈F$.
Our goal is to construct a family $B_β = *β | β∈$ of mixing unitaries (cf. \Cref{def:feas_reach}) with respect to the constraints in \cref{eq:adjacent_nodes} and \cref{eq:hamming_weight}.
To this end, we follow the procedure described by \textcite{hadfield_diss}.
We start by constructing local and classical mixing rules and continue by translating those to unitary operators.\\
Starting with a feasible schedule $x$, we want the Hamming weight $x$ to be invariant under application of the mixing operators.
This is ensured by only applying permutations $π∈S^N$ to the indices of a bit string, i.e. $π(x) x_π^-1(1),…,x_π^-1(N)$.
The corresponding permutation unitaries
\begin{equation}
U_{\pi}\ket{\vb{x}} = \ket{\pi\of{\vb{x}}}
\end{equation}
can be extended to a family of unitaries
\begin{equation}\label{eq:fractional_permutation_unitary}
U_\pi(\beta) = \cos\of{\beta} \OneOp - \imun \sin\of{\beta}U_\pi
\end{equation}
which preserves the constraint \cref{eq:hamming_weight}.
%    While this definition is very similar to and motivated by the fractional \textsc{SWAP} gate $\cos\of{\beta} \OneOp - \imun \sin\of{\beta}\mathrm{\textsc{SWAP}}$, there is an important difference.
%    Other than the fractional \textsc{SWAP}, $U_\pi(\beta)$ is not a 1-parameter group of unitaries, meaning that in general $U_\pi(\alpha +\beta) \neq U_\pi(\alpha)U_\pi(\beta)$.
%    This is due to the fact that in general $U_\pi^2 \neq \OneOp$.
%    Note that for $\beta = (2n+1)\frac{\pi}{2}$ with $n\in\N$, $U_\pi(\beta)\propto U_\pi$ is just the permutation unitary up to a global phase.
In order to preserve the constraint \cref{eq:adjacent_nodes} we check whether a permutation will preserve the constraint via a boolean function $χ 0,1^k→0,1$ which decides if an input bit string (with an auxiliary bit attached) is feasible or not.
Given a unitary operator $U$ acting on $k'$ qubits, we define the $χ$-controlled unitary operator (see \cite[p.145]{hadfield_diss}) $Λ_χU$ acting on $k+k$ qubits by the linear extension of
\begin{equation}\label{eq:controlled_unitary}
\Lambda_{\chi}\of{U}\ket{x}\ket{y} = \begin{cases}
\ket{x}\ket{y}, & \chi\of{y}=0\\ (U\ket{x})\ket{y}, & \chi\of{y}=1
\end{cases}
\end{equation}
defined for computational basis states $|x⟩$ and $|y⟩$ given by $x∈0,1^k, y∈0,1^k'$.
If we find a function $χ_π$ for each $π$ such that $χ_π(x)=1$ if and only if $π(x)$ satisfies \cref{eq:graph_constraints}, we can use it as the control for the permutation unitary $U_π(β)$.
Denote the neighborhood of a vertex $j∈V$ by $j = *k∈V | (j,k)∈E$.
If $x_j=0$ there will be no conflict with the constraint regarding $x_π(j)$ even if other nodes in $(π(j))$ are 1.
On the other hand if $x_j = 1$ all neighbors of $π(j)$ need to be 0 after the permutation is applied in order for $π$ not to raise a conflict.
Hence, to prevent conflicts regarding node $j$ we compute
\begin{equation}\label{eq:single_classical_control}
\chi_\pi^j\of{x} = \lnot(x_j) \lor \of{\bigwedge_{l\in\nbhd(\pi(j))}\lnot(x_{\pi\inv(l)})}.
\end{equation}

Now we can define the complete classical control predicate
\begin{equation}\label{eq:full_classical_control}
\begin{aligned}
\chi_\pi\of{x} 	&= \bigwedge_{j=1}^N \chi_\pi^j\of{x}.
\end{aligned}
\end{equation}

\begin{definition}[Partial graph-controlled permutation mixers]\label{def:partial_mixers}
For every permutation $\pi\in S^N$ define a \emph{partial graph-controlled permutation mixer}
\begin{equation}\label{eq:partial_mixers}
% {\mix}_{\pi}(\beta) =
\Lambda_{\chi_{\pi}}\of{\tilde U_{\pi}\of{\beta}},
\end{equation}
where $\chi_{\pi}$ is the control function defined in \cref{eq:full_classical_control} and
\begin{equation}\label{eq:fractional_permutation_unitary_altered}
\tilde U_\pi\of{\beta} \mDef \cos{\beta}(\OneOp\otimes\OneOp) - \imun \sin{\beta}(X\otimes U_\pi)
\end{equation}
is a version of \cref{eq:fractional_permutation_unitary} which is controlled on an auxiliary qubit $\ket{c}$, whose purpose is explained below, cf. \Cref{fig:control_circuit}.
\end{definition}

We present one possible approach for implementing the partial graph-controlled permutation mixers \eqref{eq:partial_mixers}.
We assume that an implementation of $Ũ_πβ$ controlled by a single qubit (see below) is known and focus primarily on the implementation of the graph-control.
\begin{center}\label{fig:controlled_U_tilde}
\begin{quantikz}
\qw & \ctrl{1} & \qw\\
\qw & \gate{\tilde U_\pi\of{\beta}} & \qw
\end{quantikz}
\end{center}

We explicitly implement the logic of $χ_π$ \eqref{eq:full_classical_control} using additional $3N+2$ auxiliary qubits.
Take some $x∈0,1^N$ and consider $3$ $N$-qubits auxiliary quantum registers $y, a, b$ with initial states $|0⟩_y$, $|0⟩_a$ and $|0⟩_b$ and one-qubit registers with initial states $|0⟩_c$ and $|0⟩_z$ of one qubit each.
% If not stated otherwise, all auxiliary qubits will be assumed to be instantiated in $\ket 0$.
The register $y$ will contain information on the main working register $x$.
Each of the remaining auxiliary registers will represent truth values of intermediate results in the calculation of $χ_πy$. An overview of the purpose of each register can be found in  \cref{table:registers}.
Following the construction of sequential mixers presented in \cite{hadfield_diss} we state the following definition for the mixer operators $(β)$.
\begin{definition}[Graph-controlled permutation mixers]\label{def:permutation_mixers}
Define the sequential mixer
\begin{equation}\label{eq:permutation_mixers}
\mix(\beta) \coloneqq \left( \prod_{\pi\in P \subset S^N}\mix_{\pi}(\beta)\right) A \,,
\end{equation}
where $A$ and $B_\pi\of{\beta}$ defined as in \Cref{fig:control_circuit} and $P$ is a suitable subset of permutations; a natural choice is presented in \Cref{lemma:transpositions}.
More precisely, in order to implement $\mix (\beta)$ apply \dots
\begin{enumerate}[label=(\alph{*})]
\item \dots $A$ as defined in \Cref{fig:control_circuit}, i.e. for each $j=1,\dots,N$ apply $\textsc{CNOT}_{j;j}\ket{\psi}_x\otimes\ket{0}_y$, where $\ket{\psi}_x$ is a superposition of feasible states in the main register. This step copies an unmodified version of the working register into the $y$ register.
\item \dots a Pauli $X_j$ on each qubit $b_j$, $j=1,\dots,N$ in the register $b$, flipping the qubits in the $b$ register.
\item \dots $C_j\of{\pi}$ for each $j=1,\dots, N$ as defined in \cref{eq:control_circuits}.
This step first uses each qubit $a_j$ in the $a$ register to store whether there are any neighbors of $\pi(j)$ which have the value $1$ in the constraint graph corresponding to the schedule which applying $\pi$ would yield. Then the bit $b_j$ is flipped back to $0$ if $a_j$ has the value $0$ and $y_j$ has the value $1$, i.e. if a conflict (two neighboring vertices in the constraint graph both have value $1$) regarding the $j$-th variable arises. This implements the logic in \cref{eq:single_classical_control}.
%, i.e. apply $\textsc{CNOT}_{\lnot l_1,\dots,\lnot l_{d\of{j}};j}\ket{y}\otimes \ket{a}$, for $\nbhd\of{\pi\of j} = \cof{\pi^{-1} \of{l_1},\dots,\pi^{-1} \of{l_{d\of{j}}}}$ and $\textsc{CNOT}_{j,\lnot j;j}\ket{y}\otimes \ket{a}\otimes\ket{b}$.

\item \dots a single multiqubit $\textsc{CNOT}_{1,\dots,N,\lnot N+1; 1}$ applied to the registers $b$ and $c$ (control qubits) and $z$. This stores in the register $z$ whether all qubits in $b_j$ have the value $1$, i.e. if applying the permutation would yield a feasible schedule. This is the implementation of \cref{eq:full_classical_control}.
\item \dots a single qubit controlled $\tilde U_\pi\of{\beta}$ as defined in \cref{eq:fractional_permutation_unitary_altered}, applied to the registers $c$ and $x$ with $\ket{z}$ as control qubit.
This applies the parameterized permutation, conditioned on register $z$ (which indicates whether the permutation is feasible) and register $c$, which ensures that the permutation is only applied to the original $\ket{\psi}_x$ portion of the working register.
\item Uncompute the auxiliary registers as depicted in \Cref{fig:control_circuit}, i.e. apply the inverse operator of (b)-(e).
\item Repeat (b)-(f) for every $\pi\in P\subset S^N$.
\end{enumerate}

\begin{table}[ht!]
\caption{Quantum registers and their purpose}
\begin{center}
\begin{tabular}{ |c|p{0.55\linewidth}|c| }
\hline
$y$ & Aux. register: Copy of the initial state before the application of any permutations in the main register & $N$ qubits \\
\hline
$a$ & Aux. register: For each variable $x_j$: would rescheduling according to $\pi \in S_N$ lead to the assignment $x_{l}=0$ for every neighbor $l$ of $\pi(j)$? & $N$ qubits\\
\hline
$b$ & Aux. register: If $a_j=1$ (else set $b_j:=1$): would rescheduling according to $\pi \in S_N$ lead to the assignment $x_{\pi{j}}=1$? & $N$ qubits\\
\hline
$z$ & Aux. register: Are all of the variables in register $b$ equal to $1$  & $1$ qubit \\
\hline
$c$ &  Aux. register: One variable ensuring that each layer only applies permutations to the original state & $1$ qubit \\
\hline
$x$ & Main register: Modified by every time we apply $B_\pi(\beta)$ for a permutation yielding a legal schedule  & $N$ qubits \\
\hline
\end{tabular}
\label{table:registers}
\end{center}
\end{table}

Here $\textsc{CNOT}_{l_1,\dots,l_n;k}$ denotes the multi qubit \textsc{CNOT} acting on qubits $l_1,\dots,l_n$ as control and on qubit $k$ as target.
A \glqq{}$\lnot$\grqq{} in an expression like $\textsc{CNOT}_{i,\lnot j;k}$ denotes that the $j$-th qubit should act as negated control qubit, while the $i$-th qubit should act as normal control.
The number of neighbors of a node $j$ in the graph is denoted by $d(j)$.
% Negated control means, that the target state gets flipped, if all control qubits are in the $0$ state instead of the $1$ state.
The whole procedure is illustrated in \Cref{fig:control_circuit},
\begin{figure*}
\centering
\begin{quantikz}
\lstick{$\ket{0}_y$}\qwbund{}& \targ{}\qwbund{}\gategroup[wires=6, steps=1, style={dashed,rounded corners, inner xsep=2pt}]{$A$}
&\qwbund{}   &\qwbund{}\gategroup[wires=6, steps=12,style={dashed,rounded corners, inner xsep=2pt}]{$\mix_\pi\of{\beta}$}%
& \gate[wires=3, bundle={2,3} ]{\rotatebox{90}{$C_1\of{\pi}$}} \qwbund{} %
&  \ \ldots\ \qwbund{} %
& \gate[wires=3,bundle={2,3} ]{\rotatebox{90}{$C_N\of{\pi}$}}\qwbund{}          & \qwbund{}     & \qwbund{}                     &\qwbund{} &\qwbund{}
& \gate[wires=3, bundle={2,3} ]{\rotatebox{90}{$C_N\of{\pi}$}} \qwbund{} %
&  \ \ldots\ \qwbund{} %
&\gate[wires=3,bundle={2,3} ]{\rotatebox{90}{$C_1\of{\pi}$}}\qwbund{}     &\qwbund{} &\qwbund{}             \\
\lstick{$\ket{0}_a$} &\qwbund{}                &  \qwbund{} &\qwbund{}          &         &\ \ldots\ \qwbund{}&         & \qwbund{}     & \qwbund{}                     &\qwbund{} &\qwbund{}&         &\ \ldots\ \qwbund{}&          &\qwbund{} &\qwbund{}
\\
\lstick{$\ket{0}_b$} &\qwbund{}                &\qwbund{}   &  \gate{X}\qwbund{}&         &\ \ldots\ \qwbund{}&         & \ctrlbundle{1}& \qwbund{}                     & \ctrlbundle{1} &\qwbund{}&         &\ \ldots\ \qwbund{}&         &  \gate{X}\qwbund{}&\qwbund{}
\\
\lstick{$\ket{0}_z$}        &\qw                      &\qw         &\qw                &\qw      & \qw      &\qw      &\targ{}\qw   &\ctrl{1}\qw                         &\targ{}\qw    &\qw     &\qw         &\qw                &\qw       &\qw &\qw
\\
\lstick{$\ket{0}_c$} &\qw                      &  \qw       &\qw                &  \qw    &   \qw    & \qw     & \octrl{-1}       & \gate[wires=2, bundle={2}]{\tilde U_\pi\of{\beta}}\qw                       & \octrl{-1} &\qw      &\qw      &\qw    & \qw       &\qw  &\qw
\\
\lstick{$\ket{\psi}_x$}  &\ctrlbundle{-5}\qwbund{} &\qwbund{}   &  \qwbund{}        &\qwbund{}& \qwbund{}&\qwbund{}& \qwbund{}     & \qwbund{}&\qwbund{}& \qwbund{}    &\qwbund{}& \qwbund{}    &\qwbund{}&\qwbund{}&\qwbund{}
\end{quantikz}
\caption{
The quantum circuit of $B_{\pi}\of{\beta}A$ used for graph-controlled permutation mixers $\mix(\beta)$ from \Cref{def:permutation_mixers}. The $C_j\of{\pi}$ are defined in \cref{eq:control_circuits} and $\tilde U_\pi\of\beta$ is defined in \cref{eq:fractional_permutation_unitary_altered}. The auxiliary registers are initialized in the zero state, the working register contains a superposition of feasible states $\ket{\psi}_x$.
\label{fig:control_circuit}
\end{figure*}
where $C_j\of{\pi}$ is defined in \cref{eq:control_circuits}.
\begin{equation}\label{eq:control_circuits}
\begin{quantikz}
\lstick{$y$} \qwbund& \gate[wires=3,bundle={2,3} ]{C_j\of{\pi}} \qwbund & \qwbund &   \\
\lstick{$a$} \qwbund&                                  \qwbund & \qwbund &   \\
\lstick{$b$} \qwbund&                                  \qwbund & \qwbund &
% &&&
\end{quantikz}
\coloneqq
\begin{quantikz}
\lstick{$y_{j}$}             \qw &   \qw         &    \qw                & \ctrl{2}      &   \qw \\
\lstick{$y_{P_j}$}   \qwbundle{}  &   \qwbundle{d\of{\pi\of{j}}}     &    \octrl{1}    & \qwbundle{}   &   \qwbundle{} \\
\lstick{$a_j$}               \qw &   \qw         &    \targ{}            & \octrl{1} &   \qw \\
\lstick{$b_j$}               \qw &   \qw         &    \qw                & \targ{}   &   \qw
\end{quantikz}\,,
\end{equation}
where $P_j \coloneqq \pi^{-1}\of{\nbhd\of{\pi(j)}}$.
\end{definition}
Note that the uncomputation leads to the states $|0⟩$ only in registers $a$ and $b$. For the auxiliary registers $y$, $c$ and $z$, we require a fresh register for each layer of mixers. Thus, this protocol requires $2N + (2+N)k$ auxiliary registers in total for $N$ logical qubits and $k$ layers in \qaoa.

There are several options to choose a suitable set of permutations $P$. Considering the entire set $S^N$ fulfills all requirements of \Cref{def:feas_reach} but is practically infeasible since it would require checking $|S^N|= N!$, i.e. factorially many permutations.
The following lemma states that it is sufficient to restrict to transpositions.
\begin{lemma}\label{lemma:transpositions}
Given feasible schedules $x,y \in F \subset \{0,1\}^N$, there are transpositions $\tau_1,...,\tau_k \in S_N$ such that
\begin{equation}
\left(\prod_{i=1}^{k}\tau_i\right)(x)=y \text{ and } \left(\prod_{i=1}^{l}\tau_i\right)(x) \in F
\end{equation}
for each $1 \leq l \leq k$.
\end{lemma}
\begin{proof}
Assume that the makespans $C(x)$, $C(y)$ of schedules $x$ and $y$ satisfy $\max(C(x), C(y))<\frac{1}{2}n_T$, else choose a higher cutoff for number of steps $n_T$.\\
Let $j \in J$ and $o \in O_j$ specify a job and an operation. Without loss of generality, we assume that the bijective enumeration function $\iota: O \times M \times T \rightarrow \{1,\dots,N\}$ is built such that $\iota(o,m,2t) = 2\iota(o,m,t)$. Define indices $b_{j,o}, c_{j,o} \in \{1,\dots,N\}$ such that
\begin{equation}\label{eq:b_jo}
\iota^{-1}(b_{j,o}) = (j,o,m,t) \text{ for some } m \text{, } t \text{ and } x_{b_{j,o}}=1
\end{equation}
\begin{equation}\label{eq:c_jo}
\iota^{-1}(c_{j,o}) = (j,o,m',t') \text{ for some } m' \text{, } t' \text{ and } y_{c_{j,o}}=1.
\end{equation}
In other words $b_{j,o}$ and $c_{j,o}$ are the indices corresponding to operation $o$ of job $j$ whose entry in the schedule $x$ resp. $y$ is $1$. As every feasible schedule assigns an operation to exactly one machine and starting time, the properties \eqref{eq:b_jo} and \eqref{eq:c_jo} characterize $b_{j,o}$ and $c_{j,o}$ uniquely.

Define transpositions $\tau_{j,o}^{1 \rightarrow 2}, \tau_{j,o}^{2 \rightarrow 1} \in S_N$ via
\begin{equation}
\tau_{j,o}^{1 \rightarrow 2}(a) =
\begin{cases}
2a & \text{ if } a = b_{j,o}\\
\frac{a}{2} & \text{ if } \frac{a}{2} = b_{j,o}\\
a & \text{ otherwise}
\end{cases}
\end{equation}
\begin{equation}
\tau_{j,o}^{2 \rightarrow 1}(a) =
\begin{cases}
c_{j,o} & \text{ if } \frac{a}{2} = b_{j,o}\\
2b_{j,o} & \text{ if } a = c_{j,o}\\
a & \text{ otherwise.}
\end{cases}
\end{equation}
$\tau_{j,o}^{1 \rightarrow 2}$ is the transposition which shifts the assignment of operation $(j,o)$ according to schedule $x$ into the second half of the available time window. The transposition $\tau_{j,o}^{2 \rightarrow 1}$ shifts the assignment of operation $(j,o)$ back into the first half of the available time window, but into the position specified by the goal schedule $y$.
Now, we define an order in which we apply the transpositions $\tau_{j,o}^{1 \rightarrow 2}$ and $\tau_{j,o}^{2 \rightarrow 1}$ for each job and operation $(j,o)$. We first apply $\tau_{j,o}^{1 \rightarrow 2}$ and within every job $j$, we go from last to first operation, thereby ensuring that the order constraint is satisfied at all times.
\begin{equation}
\pi := \prod_{j \in J} \prod_{o=1}^{O_j} \tau_{j,o}^{1 \rightarrow 2}\,.
\end{equation}
In the second step, we apply the transpositions $\tau_{j,o}^{2 \rightarrow 1}$, this time going from first to last operation within each job.
\begin{equation}
\rho := \prod_{j \in J} \prod_{o=O_j}^{1} \tau_{j,o}^{2 \rightarrow 1}\,.
\end{equation}
In total, we get the desired result
\begin{equation}
\rho \pi (x) = y\,.
\end{equation}
\end{proof}

Now we will show that the mixing operators given in \Cref{def:permutation_mixers} preserve feasibility with respect to the constraints \eqref{eq:graph_constraints}.
This implies that, when starting in a feasible state and running \qaoa, the evolution stays in the feasible subspace of the given problem.
There will be no overlaps with non-feasible states and the algorithm is exclusively focused on optimizing with regard to a given goal function. In the following, we denote the Hilbert space of the auxiliary registers by $ℋ_aux(^2)^⊗(3N+2)$ and $|0⟩_aux⊗_i=1^3N+2|0⟩$.
\begin{theorem}\label{thm:feasibility}(\textit{Preserving feasibility}).
The mixer operators $\mix(\beta)$ given in \Cref{def:permutation_mixers} preserve feasibility with regard to the constraints given in \cref{eq:graph_constraints}, i.e. for every $x\in F$, $\beta \in \R$ we have $$\mix(\beta)\left(\ket{x}\otimes \ket{0}_{\text{aux}}\right) \in\feas\otimes \mathcal{H}_{\text{aux}}\,.$$
\end{theorem}
\begin{proof}
Given any list of permutations $\pi_1,...,\pi_n \in S_N$, the quantum state after applying $\prod_i B_{\pi_i}(\beta)A$ to a feasible initial basis state $\ket{x}$ with $x\in F$ is given by
\begin{align*}
&\left( \prod_{i=1}^n B_{\pi_i}(\beta) \right) A \left(\ket{x}_x \otimes \ket{0}_{\text{aux}}\right) = \\
&\left( \prod_{i=1}^n B_{\pi_i}(\beta) \right) \left(\ket{x}_x \otimes \ket{x}_y \otimes \ket{0}_{a,b,z,c}\right) = \\
&\alpha \left(\ket{x}_x \otimes \ket{x}_y \otimes \ket{0}_{a,b,z,c}\right) + \\
&\sum_{i=1}^n \alpha_i \left(\ket{\pi_i(x)}_x \otimes \ket{x}_y \otimes\ket{0}_{a,b}\otimes \ket{\text{trash}(i)}_{z,c}\right),
\end{align*}
where $\alpha_i = 0$ iff $\pi_i(x)$ is not a feasible solution. This is ensured by construction of the control logic with auxiliary registers $a,b,y$ and $z$. The control on auxiliary register $c$ ensures by construction that a permutation $\pi_i$ is only ever applied to the initial $\ket{x}$ portion of the superposition in the main register, cf. \Cref{fig:control_circuit}.
\end{proof}
The second criterion $$ needs to meet in order for being a suitable mixer is that every feasible basis state in $$ can be reached by a number of repetitions.
This is necessary for the phase-separator to have access to all possible solutions in order to find the best possible one.
In fact, $$ as given in \Cref{def:permutation_mixers} does have this property. We define $|0⟩_aux,k⊗_i=1^2N+(N+2)k|0⟩$.

\begin{theorem}\label{thm:explorability}(\textit{Exploring the feasible subspace}).
Let $x\in F$, denote the initial state in the auxiliary registers as $\ket{0}_{\text{aux},k}\in \mathcal{H}_{\text{aux},k}$, the mixer $\mix(\beta)$ as given in \Cref{def:permutation_mixers} and $\ket{\psi_{\text{mix}, k, \beta}(x)} \coloneqq \left(\mix(\beta)\right)^k\left(\ket{x}\otimes \ket{0}_{\text{aux,k}}\right)$. Further define $\rho^x_{\text{mix}, k, \beta}\coloneqq \Tr_{\text{aux}}{\left[\ketbra{\psi_{\text{mix}, k, \beta}(x)}{\psi_{\text{mix}, k, \beta}(x)}\right]}$. Then for every $x,x\primed\in F$ there are some $k\in\N$ and $\beta\in \R$  s.t.
$$\Tr\left[\ketbra{x\primed }{x\primed }\rho^x_{\text{mix}, k, \beta}\right]>0\,.$$
\end{theorem}
\begin{proof}
Let $x,x\primed \in F$. Denote the transpositions provided by \Cref{lemma:transpositions} by $\tau_1,...,\tau_k \in S_N$ and recall their properties
\begin{equation}\label{eq: taus in proof of explorability}
\left(\prod_{i=1}^{k}\tau_i\right)(x)=x' \text{ and } \left(\prod_{i=1}^{l}\tau_i\right)(x) \in F
\end{equation}
for each $ 1 \leq l \leq k$. Then
\begin{align*}
&\ket{\psi_{\text{mix}, k, \beta}(x)} = \left(\mix(\beta)\right)^k  \left(\ket{x}\otimes \ket{0}_{\text{aux,k}}\right) \\
&= \alpha \ket{\tau_k\cdots \tau_1 (x)}\otimes  \ket{0}_{a,b}\otimes \ket{\text{trash}}^{\otimes k}_{y,z,c} + \ket{\text{rest}} \\
& = \alpha \ket{x'}\otimes  \ket{0}_{a,b}\otimes \ket{\text{trash}}^{\otimes k}_{y,z,c} + \ket{\text{rest}},
\end{align*}
where $\alpha =\prod_{j=1}^k \alpha_j$, $\alpha_j>0$ being the probability that we apply $\tau_j$ in the $j$-th layer. The remaining sum of feasible states $\ket{\text{rest}}$ may possibly contain a summand with $\ket{x'}$, so we choose $\beta$ such that it does not cancel out the coefficient $\alpha$. Denote the state in the auxiliary registers corresponding to $x'$ by $\ket{\psi (x')}_{\text{aux}} \coloneqq \ket{0}_{a,b}\otimes \ket{\text{trash}}^{\otimes k}_{y,z,c}$ as derived above. Then the probability of obtaining $\ket{\psi (x')}_{\text{aux}}$ when measuring the auxiliary registers of $\ket{\psi_{\text{mix}, k, \beta}(x)}$ in the computational basis is given by $P(\ket{\psi (x')}_{\text{aux}})>0$. Thus, for a suitable choice of $\beta$ and $k$ as chosen in \cref{eq: taus in proof of explorability} we have
\begin{align*}
\Tr\left[\ketbra{x\primed }{x\primed }\rho^x_{\text{mix}, k, \beta}\right]=
P\left(\ket{\psi (x')}_{\text{aux}}\right)\alpha^2 > 0\,.
\end{align*}
\end{proof}

\section{Discussion and Outlook}\label{sec:discussion}
We have introduced mixer operators for the \fjsp{} and have proven that they preserve feasibility and explore the entire feasible subspace.
While the considered constraint graph model is the same as the one considered by \textcite{hannover_paper}, the general approach is very different.
The work by \textcite{hannover_paper} has implicitly shown, that for the \fjsp{} permutation unitaries are not sufficient to construct mixing unitaries in the sense of \textcite{hadfield_diss}, when no auxiliary qubits are used.
In this work, we employ several auxiliary registers in order to ensure that the emerging mixing unitaries preserve the feasible subspace.
In general, the described control protocol may be applied to all problems that can be modelled by a constraint graph. Additionally, our construction includes a few tricks which can be reused in other protocols, such as the auxiliary register $c$ which stores the information whether an operator has been applied to the quantum state, thus avoiding that a product of permutations is applied. The direct implementation of constraints in the operators $C_i$ can be used whenever constraints admit a boolean formulation as in \cref{eq:single_classical_control}.
\newline
The practicality of the presented mixing operators can be debated critically. The direct implementation $C_1 …C_N$ of the control logic adds an overhead of $𝒪 N^3$ Toffoli, \textsc CNOT and single qubit gates to the single qubit controlled $U_π$. In total, the mixer operator $β$ applies at least $𝒪(N^2) 𝒪N^3 + n_p = 𝒪N^5 + n_p 𝒪N^2$ Toffoli, \textsc CNOT and single qubit gates, where $n_p = min*n_π| π∈S^N$ denotes the minimal number of basic gates necessary to implement the single qubit controlled $U_π$. This results in a polynomial gate count, which we suspect, however, to be quite demanding on current quantum systems, considering their limited coherence times.
A direction for further research could be to exploit the logical structure of specific constraints in order to enforce these in a more efficient way. For certain types of constraints, this has been achieved by \cite{CM_QAOA_Fuchs2022}. Also, one could employ a hybrid approach, where some constraints are enforced via efficiently constructed constraint mixers, while for others the more common penalty term method is kept in place.
Further, numerical simulations may give more insight on the potential of approaches using constraint mixers.
Also, a combination of both the direct approach presented in this work and the abstract analysis of the constraint-graph \parencite{hannover_paper} could reduce the number of necessary gates and result in an applicable set of mixing unitaries for solving the \fjsp{} with the \qaoa{}.
This can be possibly achieved following \cite{Meyer_2023}, which presents a concrete method to design variational circuits which take into account problem symmetries.
\newline
Another way to reduce the number of auxiliary qubits as well as the gate complexity of one single $_π$ \eqref{eq:partial_mixers}, might be a deeper analysis of the logarithm of the fractional permutation unitaries \eqref{eq:fractional_permutation_unitary}. Finding a general logarithm for these unlocks a different control implementation by considering the exponential of the tensor product of the logarithm and the Hamiltonian simulating the classical control logic.

\section*{Acknowledgements}
The authors thank L. Binkowski, J. R. Fin\v zgar, C. B. Mendl, T. Osborne and B. Poggel for fruitful discussions and comments.
LP and MH acknowledge financial support
by the BMBF project QuBRA.

\vspace{2cm}

% if added before the last page, this command can help balancing columns

% % $ biblatex auxiliary file $
% $ biblatex bbl format version 3.1 $
% Do not modify the above lines!
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated by
% biber as required.
\begingroup
\makeatletter
\<EMAIL_ADDRESS>{Missing 'biblatex' package}
{The bibliography requires the 'biblatex' package.}
\aftergroup\endinput}
\endgroup

\refsection{0}
\datalist[entry]{apa/global//global/global}
\entry{Cerezo_2021}{article}{}
\name{author}{11}{}{%
given={Simon\bibnamedelima C.},
giveni={S\bibinitperiod\bibinitdelim C\bibinitperiod},
given={Jarrod\bibnamedelima R.},
giveni={J\bibinitperiod\bibinitdelim R\bibinitperiod},
given={Patrick\bibnamedelima J.},
giveni={P\bibinitperiod\bibinitdelim J\bibinitperiod},
\list{publisher}{2}{%
{Springer Science}%
{Business Media {LLC}}%
\strng{namehash}{9f3fe252c8e07ea798c5758094bc02cd}
\strng{fullhash}{aeb54beafe59128c13a6651991958563}
\strng{bibnamehash}{aeb54beafe59128c13a6651991958563}
\strng{authorbibnamehash}{aeb54beafe59128c13a6651991958563}
\strng{authornamehash}{9f3fe252c8e07ea798c5758094bc02cd}
\strng{authorfullhash}{aeb54beafe59128c13a6651991958563}
\field{sortinit}{C}
\field{sortinithash}{4c244ceae61406cdc0cc2ce1cb1ff703}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{Nature Reviews Physics}
\field{month}{8}
\field{number}{9}
\field{title}{Variational quantum algorithms}
\field{volume}{3}
\field{year}{2021}
\field{pages}{625\bibrangedash 644}
\range{pages}{20}
\verb{doi}
\verb 10.1038/s42254-021-00348-9
\endverb
\verb{urlraw}
\verb https://doi.org/10.1038%2Fs42254-021-00348-9
\endverb
\verb{url}
\verb https://doi.org/10.1038%2Fs42254-021-00348-9
\endverb
\endentry
\entry{farhi_qaoa}{misc}{}
\name{author}{3}{}{%
\list{publisher}{1}{%
\strng{namehash}{4678a579c5851929a69bc0b9a15a0a83}
\strng{fullhash}{20254ebc49b7f7e3467958f0e39320cd}
\strng{bibnamehash}{20254ebc49b7f7e3467958f0e39320cd}
\strng{authorbibnamehash}{20254ebc49b7f7e3467958f0e39320cd}
\strng{authornamehash}{4678a579c5851929a69bc0b9a15a0a83}
\strng{authorfullhash}{20254ebc49b7f7e3467958f0e39320cd}
\field{sortinit}{F}
\field{sortinithash}{fb0c0faa89eb6abae8213bf60e6799ea}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{A Quantum Approximate Optimization Algorithm}
\field{year}{2014}
\verb{doi}
\verb 10.48550/ARXIV.1411.4028
\endverb
\verb{urlraw}
\verb https://arxiv.org/abs/1411.4028
\endverb
\verb{url}
\verb https://arxiv.org/abs/1411.4028
\endverb
\keyw{Quantum Physics (quant-ph),FOS: Physical sciences,FOS: Physical sciences}
\endentry
\entry{CM_QAOA_Fuchs2022}{article}{}
\name{author}{5}{}{%
given={Franz\bibnamedelima Georg},
giveni={F\bibinitperiod\bibinitdelim G\bibinitperiod},
given={Kjetil\bibnamedelima Olsen},
giveni={K\bibinitperiod\bibinitdelim O\bibinitperiod},
family={MÃ¸ll\bibnamedelima Nilsen},
familyi={M\bibinitperiod\bibinitdelim N\bibinitperiod},
given={Alexander\bibnamedelima Johannes},
giveni={A\bibinitperiod\bibinitdelim J\bibinitperiod},
\strng{namehash}{7f8185b74ebcdea8e7cb538e5d61d029}
\strng{fullhash}{7a4a7cc392519b036563aedac4044610}
\strng{bibnamehash}{7a4a7cc392519b036563aedac4044610}
\strng{authorbibnamehash}{7a4a7cc392519b036563aedac4044610}
\strng{authornamehash}{7f8185b74ebcdea8e7cb538e5d61d029}
\strng{authorfullhash}{7a4a7cc392519b036563aedac4044610}
\field{sortinit}{F}
\field{sortinithash}{fb0c0faa89eb6abae8213bf60e6799ea}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{abstract}{The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the “XY”-mixer designed to preserve the subspace of “one-hot” states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an “XY”-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.}
\field{issn}{1999-4893}
\field{journaltitle}{Algorithms}
\field{number}{6}
\field{title}{Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm}
\field{volume}{15}
\field{year}{2022}
\verb{doi}
\verb 10.3390/a15060202
\endverb
\verb{urlraw}
\verb https://www.mdpi.com/1999-4893/15/6/202
\endverb
\verb{url}
\verb https://www.mdpi.com/1999-4893/15/6/202
\endverb
\endentry
\entry{grover1996fast}{misc}{}
\name{author}{1}{}{%
given={Lov\bibnamedelima K.},
giveni={L\bibinitperiod\bibinitdelim K\bibinitperiod},
\strng{namehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{fullhash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{bibnamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authorbibnamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authornamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authorfullhash}{619ef89ee12058aba6b0df9b17b11ca3}
\field{sortinit}{G}
\field{sortinithash}{62eb2aa29549e4fdbd3cb154ec5711cb}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{eprintclass}{quant-ph}
\field{eprinttype}{arXiv}
\field{title}{A fast quantum mechanical algorithm for database search}
\field{year}{1996}
\verb{eprint}
\verb quant-ph/9605043
\endverb
\endentry
\entry{hadfield_diss}{misc}{}
\name{author}{1}{}{%
\list{publisher}{1}{%
\strng{namehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{fullhash}{51e691975c42c1f9efd494b455acb7e5}
\strng{bibnamehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{authorbibnamehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{authornamehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{authorfullhash}{51e691975c42c1f9efd494b455acb7e5}
\field{sortinit}{H}
\field{sortinithash}{6db6145dae8dc9e1271a8d556090b50a}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Quantum Algorithms for Scientific Computing and Approximate Optimization}
\field{year}{2018}
\verb{doi}
\verb 10.48550/ARXIV.1805.03265
\endverb
\verb{urlraw}
\verb https://arxiv.org/abs/1805.03265
\endverb
\verb{url}
\verb https://arxiv.org/abs/1805.03265
\endverb
\keyw{Quantum Physics (quant-ph),FOS: Physical sciences,FOS: Physical sciences}
\endentry
\entry{hannover_paper}{misc}{}
\name{author}{3}{}{%
\list{publisher}{1}{%
\strng{namehash}{5e4c5e6f761e50e783dff436aae1c015}
\strng{fullhash}{edbcb180a7af38232a590bd33b42b72b}
\strng{bibnamehash}{edbcb180a7af38232a590bd33b42b72b}
\strng{authorbibnamehash}{edbcb180a7af38232a590bd33b42b72b}
\strng{authornamehash}{5e4c5e6f761e50e783dff436aae1c015}
\strng{authorfullhash}{edbcb180a7af38232a590bd33b42b72b}
\field{sortinit}{K}
\field{sortinithash}{d3edc18d54b9438a72c24c925bfb38f4}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Free Job-Shop Scheduling With Hardcoded Constraints}
\field{year}{2022}
\verb{doi}
\verb 10.48550/ARXIV.2211.05822
\endverb
\verb{urlraw}
\verb https://arxiv.org/abs/2211.05822
\endverb
\verb{url}
\verb https://arxiv.org/abs/2211.05822
\endverb
\keyw{Quantum Physics (quant-ph),Mathematical Physics (math-ph),FOS: Physical sciences,FOS: Physical sciences}
\endentry
\entry{Marx2004GRAPHCP}{article}{}
\name{author}{1}{}{%
\strng{namehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{fullhash}{e31719b087ab896a11d4b30ad542eab8}
\strng{bibnamehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{authorbibnamehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{authornamehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{authorfullhash}{e31719b087ab896a11d4b30ad542eab8}
\field{sortinit}{M}
\field{sortinithash}{2e5c2f51f7fa2d957f3206819bf86dc3}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{Periodica Polytechnica Electrical Engineering}
\field{title}{GRAPH COLOURING PROBLEMS AND THEIR APPLICATIONS IN SCHEDULING}
\field{volume}{48}
\field{year}{2004}
\field{pages}{11\bibrangedash 16}
\range{pages}{6}
\endentry
\entry{Meyer_2023}{article}{}
\name{author}{7}{}{%
given={Johannes\bibnamedelima Jakob},
giveni={J\bibinitperiod\bibinitdelim J\bibinitperiod},
familyi={G\bibinithyphendelim F\bibinitperiod},
given={Antonio\bibnamedelima Anna},
giveni={A\bibinitperiod\bibinitdelim A\bibinitperiod},
\list{publisher}{1}{%
{American Physical Society ({APS})}%
\strng{namehash}{5b291b6c6fcbe6fa437eacb0bee1fdd5}
\strng{fullhash}{6b96a77d45bea13d21ec664619b0066d}
\strng{bibnamehash}{6b96a77d45bea13d21ec664619b0066d}
\strng{authorbibnamehash}{6b96a77d45bea13d21ec664619b0066d}
\strng{authornamehash}{5b291b6c6fcbe6fa437eacb0bee1fdd5}
\strng{authorfullhash}{6b96a77d45bea13d21ec664619b0066d}
\field{sortinit}{M}
\field{sortinithash}{2e5c2f51f7fa2d957f3206819bf86dc3}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{{PRX} Quantum}
\field{month}{3}
\field{number}{1}
\field{title}{Exploiting Symmetry in Variational Quantum Machine Learning}
\field{volume}{4}
\field{year}{2023}
\verb{doi}
\verb 10.1103/prxquantum.4.010328
\endverb
\verb{urlraw}
\verb https://doi.org/10.1103%2Fprxquantum.4.010328
\endverb
\verb{url}
\verb https://doi.org/10.1103%2Fprxquantum.4.010328
\endverb
\endentry
\entry{Shor_1997}{article}{}
\name{author}{1}{}{%
given={Peter\bibnamedelima W.},
giveni={P\bibinitperiod\bibinitdelim W\bibinitperiod},
\list{publisher}{1}{%
{Society for Industrial {\&} Applied Mathematics ({SIAM})}%
\strng{namehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{fullhash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{bibnamehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{authorbibnamehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{authornamehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{authorfullhash}{7082a9c99d5d51479d4cfba6bbac2d30}
\field{sortinit}{S}
\field{sortinithash}{c319cff79d99c853d775f88277d4e45f}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{{SIAM} Journal on Computing}
\field{month}{10}
\field{number}{5}
\field{title}{Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer}
\field{volume}{26}
\field{year}{1997}
\field{pages}{1484\bibrangedash 1509}
\range{pages}{26}
\verb{doi}
\verb 10.1137/s0097539795293172
\endverb
\verb{urlraw}
\verb https://doi.org/10.1137%2Fs0097539795293172
\endverb
\verb{url}
\verb https://doi.org/10.1137%2Fs0097539795293172
\endverb
\endentry
\entry{fjsp_review}{article}{}
\name{author}{5}{}{%
\strng{namehash}{778e7b15a84e6c24f8e220c786625153}
\strng{fullhash}{4708a0fec555fbb90c0c608502f3f8c8}
\strng{bibnamehash}{4708a0fec555fbb90c0c608502f3f8c8}
\strng{authorbibnamehash}{4708a0fec555fbb90c0c608502f3f8c8}
\strng{authornamehash}{778e7b15a84e6c24f8e220c786625153}
\strng{authorfullhash}{4708a0fec555fbb90c0c608502f3f8c8}
\field{sortinit}{X}
\field{sortinithash}{e90038f30fa4b9ce59606fc8347e3cc7}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{IET Collaborative Intelligent Manufacturing}
\field{month}{09}
\field{title}{Review on flexible job shop scheduling}
\field{volume}{1}
\field{year}{2019}
\verb{doi}
\verb 10.1049/iet-cim.2018.0009
\endverb
\endentry
\enddatalist
\endrefsection
\endinput

% $ biblatex auxiliary file $
% $ biblatex bbl format version 3.1 $
% Do not modify the above lines!
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated by
% biber as required.
\begingroup
\makeatletter
\<EMAIL_ADDRESS>{Missing 'biblatex' package}
{The bibliography requires the 'biblatex' package.}
\aftergroup\endinput}
\endgroup

\refsection{0}
\datalist[entry]{apa/global//global/global}
\entry{Cerezo_2021}{article}{}
\name{author}{11}{}{%
given={Simon\bibnamedelima C.},
giveni={S\bibinitperiod\bibinitdelim C\bibinitperiod},
given={Jarrod\bibnamedelima R.},
giveni={J\bibinitperiod\bibinitdelim R\bibinitperiod},
given={Patrick\bibnamedelima J.},
giveni={P\bibinitperiod\bibinitdelim J\bibinitperiod},
\list{publisher}{2}{%
{Springer Science}%
{Business Media {LLC}}%
\strng{namehash}{9f3fe252c8e07ea798c5758094bc02cd}
\strng{fullhash}{aeb54beafe59128c13a6651991958563}
\strng{bibnamehash}{aeb54beafe59128c13a6651991958563}
\strng{authorbibnamehash}{aeb54beafe59128c13a6651991958563}
\strng{authornamehash}{9f3fe252c8e07ea798c5758094bc02cd}
\strng{authorfullhash}{aeb54beafe59128c13a6651991958563}
\field{sortinit}{C}
\field{sortinithash}{4c244ceae61406cdc0cc2ce1cb1ff703}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{Nature Reviews Physics}
\field{month}{8}
\field{number}{9}
\field{title}{Variational quantum algorithms}
\field{volume}{3}
\field{year}{2021}
\field{pages}{625\bibrangedash 644}
\range{pages}{20}
\verb{doi}
\verb 10.1038/s42254-021-00348-9
\endverb
\verb{urlraw}
\verb https://doi.org/10.1038%2Fs42254-021-00348-9
\endverb
\verb{url}
\verb https://doi.org/10.1038%2Fs42254-021-00348-9
\endverb
\endentry
\entry{farhi_qaoa}{misc}{}
\name{author}{3}{}{%
\list{publisher}{1}{%
\strng{namehash}{4678a579c5851929a69bc0b9a15a0a83}
\strng{fullhash}{20254ebc49b7f7e3467958f0e39320cd}
\strng{bibnamehash}{20254ebc49b7f7e3467958f0e39320cd}
\strng{authorbibnamehash}{20254ebc49b7f7e3467958f0e39320cd}
\strng{authornamehash}{4678a579c5851929a69bc0b9a15a0a83}
\strng{authorfullhash}{20254ebc49b7f7e3467958f0e39320cd}
\field{sortinit}{F}
\field{sortinithash}{fb0c0faa89eb6abae8213bf60e6799ea}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{A Quantum Approximate Optimization Algorithm}
\field{year}{2014}
\verb{doi}
\verb 10.48550/ARXIV.1411.4028
\endverb
\verb{urlraw}
\verb https://arxiv.org/abs/1411.4028
\endverb
\verb{url}
\verb https://arxiv.org/abs/1411.4028
\endverb
\keyw{Quantum Physics (quant-ph),FOS: Physical sciences,FOS: Physical sciences}
\endentry
\entry{CM_QAOA_Fuchs2022}{article}{}
\name{author}{5}{}{%
given={Franz\bibnamedelima Georg},
giveni={F\bibinitperiod\bibinitdelim G\bibinitperiod},
given={Kjetil\bibnamedelima Olsen},
giveni={K\bibinitperiod\bibinitdelim O\bibinitperiod},
family={MÃ¸ll\bibnamedelima Nilsen},
familyi={M\bibinitperiod\bibinitdelim N\bibinitperiod},
given={Alexander\bibnamedelima Johannes},
giveni={A\bibinitperiod\bibinitdelim J\bibinitperiod},
\strng{namehash}{7f8185b74ebcdea8e7cb538e5d61d029}
\strng{fullhash}{7a4a7cc392519b036563aedac4044610}
\strng{bibnamehash}{7a4a7cc392519b036563aedac4044610}
\strng{authorbibnamehash}{7a4a7cc392519b036563aedac4044610}
\strng{authornamehash}{7f8185b74ebcdea8e7cb538e5d61d029}
\strng{authorfullhash}{7a4a7cc392519b036563aedac4044610}
\field{sortinit}{F}
\field{sortinithash}{fb0c0faa89eb6abae8213bf60e6799ea}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{abstract}{The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the “XY”-mixer designed to preserve the subspace of “one-hot” states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an “XY”-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.}
\field{issn}{1999-4893}
\field{journaltitle}{Algorithms}
\field{number}{6}
\field{title}{Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm}
\field{volume}{15}
\field{year}{2022}
\verb{doi}
\verb 10.3390/a15060202
\endverb
\verb{urlraw}
\verb https://www.mdpi.com/1999-4893/15/6/202
\endverb
\verb{url}
\verb https://www.mdpi.com/1999-4893/15/6/202
\endverb
\endentry
\entry{grover1996fast}{misc}{}
\name{author}{1}{}{%
given={Lov\bibnamedelima K.},
giveni={L\bibinitperiod\bibinitdelim K\bibinitperiod},
\strng{namehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{fullhash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{bibnamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authorbibnamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authornamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authorfullhash}{619ef89ee12058aba6b0df9b17b11ca3}
\field{sortinit}{G}
\field{sortinithash}{62eb2aa29549e4fdbd3cb154ec5711cb}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{eprintclass}{quant-ph}
\field{eprinttype}{arXiv}
\field{title}{A fast quantum mechanical algorithm for database search}
\field{year}{1996}
\verb{eprint}
\verb quant-ph/9605043
\endverb
\endentry
\entry{hadfield_diss}{misc}{}
\name{author}{1}{}{%
\list{publisher}{1}{%
\strng{namehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{fullhash}{51e691975c42c1f9efd494b455acb7e5}
\strng{bibnamehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{authorbibnamehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{authornamehash}{51e691975c42c1f9efd494b455acb7e5}
\strng{authorfullhash}{51e691975c42c1f9efd494b455acb7e5}
\field{sortinit}{H}
\field{sortinithash}{6db6145dae8dc9e1271a8d556090b50a}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Quantum Algorithms for Scientific Computing and Approximate Optimization}
\field{year}{2018}
\verb{doi}
\verb 10.48550/ARXIV.1805.03265
\endverb
\verb{urlraw}
\verb https://arxiv.org/abs/1805.03265
\endverb
\verb{url}
\verb https://arxiv.org/abs/1805.03265
\endverb
\keyw{Quantum Physics (quant-ph),FOS: Physical sciences,FOS: Physical sciences}
\endentry
\entry{hannover_paper}{misc}{}
\name{author}{3}{}{%
\list{publisher}{1}{%
\strng{namehash}{5e4c5e6f761e50e783dff436aae1c015}
\strng{fullhash}{edbcb180a7af38232a590bd33b42b72b}
\strng{bibnamehash}{edbcb180a7af38232a590bd33b42b72b}
\strng{authorbibnamehash}{edbcb180a7af38232a590bd33b42b72b}
\strng{authornamehash}{5e4c5e6f761e50e783dff436aae1c015}
\strng{authorfullhash}{edbcb180a7af38232a590bd33b42b72b}
\field{sortinit}{K}
\field{sortinithash}{d3edc18d54b9438a72c24c925bfb38f4}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Free Job-Shop Scheduling With Hardcoded Constraints}
\field{year}{2022}
\verb{doi}
\verb 10.48550/ARXIV.2211.05822
\endverb
\verb{urlraw}
\verb https://arxiv.org/abs/2211.05822
\endverb
\verb{url}
\verb https://arxiv.org/abs/2211.05822
\endverb
\keyw{Quantum Physics (quant-ph),Mathematical Physics (math-ph),FOS: Physical sciences,FOS: Physical sciences}
\endentry
\entry{Marx2004GRAPHCP}{article}{}
\name{author}{1}{}{%
\strng{namehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{fullhash}{e31719b087ab896a11d4b30ad542eab8}
\strng{bibnamehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{authorbibnamehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{authornamehash}{e31719b087ab896a11d4b30ad542eab8}
\strng{authorfullhash}{e31719b087ab896a11d4b30ad542eab8}
\field{sortinit}{M}
\field{sortinithash}{2e5c2f51f7fa2d957f3206819bf86dc3}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{Periodica Polytechnica Electrical Engineering}
\field{title}{GRAPH COLOURING PROBLEMS AND THEIR APPLICATIONS IN SCHEDULING}
\field{volume}{48}
\field{year}{2004}
\field{pages}{11\bibrangedash 16}
\range{pages}{6}
\endentry
\entry{Meyer_2023}{article}{}
\name{author}{7}{}{%
given={Johannes\bibnamedelima Jakob},
giveni={J\bibinitperiod\bibinitdelim J\bibinitperiod},
familyi={G\bibinithyphendelim F\bibinitperiod},
given={Antonio\bibnamedelima Anna},
giveni={A\bibinitperiod\bibinitdelim A\bibinitperiod},
\list{publisher}{1}{%
{American Physical Society ({APS})}%
\strng{namehash}{5b291b6c6fcbe6fa437eacb0bee1fdd5}
\strng{fullhash}{6b96a77d45bea13d21ec664619b0066d}
\strng{bibnamehash}{6b96a77d45bea13d21ec664619b0066d}
\strng{authorbibnamehash}{6b96a77d45bea13d21ec664619b0066d}
\strng{authornamehash}{5b291b6c6fcbe6fa437eacb0bee1fdd5}
\strng{authorfullhash}{6b96a77d45bea13d21ec664619b0066d}
\field{sortinit}{M}
\field{sortinithash}{2e5c2f51f7fa2d957f3206819bf86dc3}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{{PRX} Quantum}
\field{month}{3}
\field{number}{1}
\field{title}{Exploiting Symmetry in Variational Quantum Machine Learning}
\field{volume}{4}
\field{year}{2023}
\verb{doi}
\verb 10.1103/prxquantum.4.010328
\endverb
\verb{urlraw}
\verb https://doi.org/10.1103%2Fprxquantum.4.010328
\endverb
\verb{url}
\verb https://doi.org/10.1103%2Fprxquantum.4.010328
\endverb
\endentry
\entry{Shor_1997}{article}{}
\name{author}{1}{}{%
given={Peter\bibnamedelima W.},
giveni={P\bibinitperiod\bibinitdelim W\bibinitperiod},
\list{publisher}{1}{%
{Society for Industrial {\&} Applied Mathematics ({SIAM})}%
\strng{namehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{fullhash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{bibnamehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{authorbibnamehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{authornamehash}{7082a9c99d5d51479d4cfba6bbac2d30}
\strng{authorfullhash}{7082a9c99d5d51479d4cfba6bbac2d30}
\field{sortinit}{S}
\field{sortinithash}{c319cff79d99c853d775f88277d4e45f}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{{SIAM} Journal on Computing}
\field{month}{10}
\field{number}{5}
\field{title}{Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer}
\field{volume}{26}
\field{year}{1997}
\field{pages}{1484\bibrangedash 1509}
\range{pages}{26}
\verb{doi}
\verb 10.1137/s0097539795293172
\endverb
\verb{urlraw}
\verb https://doi.org/10.1137%2Fs0097539795293172
\endverb
\verb{url}
\verb https://doi.org/10.1137%2Fs0097539795293172
\endverb
\endentry
\entry{fjsp_review}{article}{}
\name{author}{5}{}{%
\strng{namehash}{778e7b15a84e6c24f8e220c786625153}
\strng{fullhash}{4708a0fec555fbb90c0c608502f3f8c8}
\strng{bibnamehash}{4708a0fec555fbb90c0c608502f3f8c8}
\strng{authorbibnamehash}{4708a0fec555fbb90c0c608502f3f8c8}
\strng{authornamehash}{778e7b15a84e6c24f8e220c786625153}
\strng{authorfullhash}{4708a0fec555fbb90c0c608502f3f8c8}
\field{sortinit}{X}
\field{sortinithash}{e90038f30fa4b9ce59606fc8347e3cc7}
\field{extradatescope}{labelyear}
\field{labeldatesource}{year}
\true{uniqueprimaryauthor}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{IET Collaborative Intelligent Manufacturing}
\field{month}{09}
\field{title}{Review on flexible job shop scheduling}
\field{volume}{1}
\field{year}{2019}
\verb{doi}
\verb 10.1049/iet-cim.2018.0009
\endverb
\endentry
\enddatalist
\endrefsection
\endinput

\end{document}