# Auditory cueing strategy for stride length and cadence modification: a
feasibility study with healthy adults

Tina LY Wu 1, Anna Murphy 2, Chao Chen 1, and Dana Kulić 1∗ *This work was
supported by the Natural Sciences and Engineering Research Council of Canada
(NSERC), Monash Institute of Medical Engineering (MIME), The Commonwealth
Scientific and Industrial Research Organisation (CSIRO), and Monash Partners.
D. Kulić was supported by an Australian Research Council Future Fellowship
(FT200100761).1Tina, Chao & Dana are with the Faculty of Engineering, Monash
University, Victoria, Australia<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>is with the Clinical Research Centre for Movement
Disorders and Gait, Monash Health, Victoria, Australia
<EMAIL_ADDRESS>
###### Abstract

People with Parkinson’s Disease experience gait impairments that significantly
impact their quality of life. Visual, auditory, and tactile cues can alleviate
gait impairments, but they can become less effective due to the progressive
nature of the disease and changes in people’s motor capability. In this study,
we develop a human-in-the-loop (HIL) framework that monitors two key gait
parameters, stride length and cadence, and continuously learns a person-
specific model of how the parameters change in response to the feedback. The
model is then used in an optimization algorithm to improve the gait
parameters. This feasibility study examines whether auditory cues can be used
to influence stride length in people without gait impairments. The results
demonstrate the benefits of the HIL framework in maintaining people’s stride
length in the presence of a secondary task.

Clinical relevance— This paper proposes a gait rehabilitation framework that
provides a personalized cueing strategy based on the person’s real-time
response to cues. The proposed approach has potential application to people
with Parkinson’s Disease.

##  I INTRODUCTION

Parkinson’s Disease (PD) is a progressive neurological disorder that affects
movement. In advanced stages of the disease, a common lower body symptom is
Freezing of Gait (FoG), where a breakdown of the person’s existing stride-
length-cadence relationship (SLCrel) occurs. In unimpaired gait, an increase
in cadence (i.e. steps per minute) is typically accompanied by an increase in
stride length (i.e. the distance travelled by the same foot) [1]. SLCrel can
exhibit a positive linear, negative linear, or negative quadratic relationship
(ibid.). When participants walk at different self-selected speeds, 90-100% of
the participants across different age groups exhibit a SLCrel (ibid.). A
freezing episode manifests as an abnormal increase in cadence with a
noticeable decrease in step length, i.e. the SLCrel breaks down [2].

The use of wearable devices to monitor the person’s gait, combined with
feedback mechanisms in the form of visual, auditory, or tactile cues, has been
shown to help people alleviate FoG [2]. Existing research on cueing mechanisms
focuses on providing on-demand cues, where visual cues at a fixed distance or
auditory/tactile cues at a fixed pace are provided at the onset of freezing
[2, 3, 4, 5]. However, few studies have focused on adapting the provision of
cues. Currently, adjustments to cues are performed by therapists during clinic
visits. The lack of cue adaptation can decrease the cue effectiveness, given
the day-to-day symptom variability and longitudinal disease progression. For
instance, people can respond to cues differently due to changes in motor
capability as part of the medication cycle [2] or may experience a decrease in
responsiveness due to habituation [6].

In this study, we extend our previous work in [7, 8] that proposes a cue-
adaptation method based on the individual’s real-time response to cues to
address symptom variability and habituation. Previous cue-adaptation methods
(e.g. [9, 10]) focus on increasing gait speed (m/s), which is influenced by
both stride length and cadence. However, the studies assume the change in gait
speed will positively influence step length and cadence. The assumption can be
detrimental in Parkinson’s as a faster gait speed can also be achieved by
increasing cadence, which could trigger FoG [11]. Our current work explicitly
models the SLCrel and provides cues that account for both gait parameters. In
our previous work, we demonstrated that auditory cues can influence cadence in
healthy adults [7] and people with PD [8]. This feasibility study focuses on
the stride length aspect of the SLCrel. The evaluation is important as
previous studies have suggested that auditory cues are not always effective in
changing stride length [12, 11]. Results from this study will inform whether a
change in cueing modality is needed and provide an initial evaluation of the
proposed HIL framework.

##  II METHODS

###  II-A Proposed Framework

We extend our previous work in [7] to incorporate monitoring of the SLCrel.
The HIL framework consists of three sub-components: an online gait parameter
estimation algorithm, a model of cue influence on gait, and an optimization
function for cue provision. The framework is illustrated in Figure 1.

Figure 1: The block diagram of the HIL framework with its user.

####  II-A1 Estimate gait parameters online

A key requirement of the HIL framework is to measure stride length in real-
time. The system needs to have fast computation and be low-cost, portable, and
easy to set up. Based on these requirements, a solution using two IMU sensors
secured onto each foot is implemented. Previously, the zero-velocity update
(ZVU) algorithm [13] had been developed to correct for sensor drift during the
stance phase of the gait cycle. To apply ZVU, we extend the method from [14],
where a dynamic threshold is computed from the accelerometer and gyroscope
signals to distinguish between the stance and swing phases. The method is
person-invariant and speed-invariant, and reduces experiment complexity (i.e.
no need to tune for each participant) and computation requirements (i.e. no
need to train on a large amount of data or need expensive hardware to run).
One benefit of real-time stance/swing detection is being able to synchronize
cues to a gait phase, similar to others such as [15]. In addition, the
detection can be used to estimate cadence (the time of the step from the start
of one swing phase to the next). However, [14] did not perform sufficient
validation with participants. We found the algorithm was not robust against
interpersonal variations and would often lead to false positives. Therefore,
we augmented the method and summarized it in Algorithm 1. The algorithm takes
each IMU sample ($\textbf{a}^{t+1},\bm{\omega}^{t+1},\textbf{q}^{t+1}$ for
accelerometer, gyroscope, and quaternion) at the current time step, $t+1$, and
returns true if it is greater than the dynamic threshold ($th_{dynamic}$).
$th_{dynamic}$ is a function of the aggregated features computed from the IMU
samples and it is the key to the person and speed-invariant algorithm. The
swing classification result is stored in the array called $is\\_swing$. Two
additional lists, called $rising\\_edge\\_list$ and $falling\\_edge\\_list$
are added as secondary filters to reject false positives.

Algorithm 1 Swing detection algorithm

Function DetectSwing($\textbf{a}^{t+1},\bm{\omega}^{t+1},\textbf{q}^{t+1}$)

Update rolling window

Compute features from the window

Aggregate features from above

if Aggregated feature $>$ $th_{dynamic}$ then

$is\\_swing^{t+1}\leftarrow True$

Initialize debounce counter

else

$is\\_swing^{t+1}\leftarrow False$

end if

if Aggregated feature $<$ $th_{static}$ then

$is\\_swing^{t+1}\leftarrow False$

Increment debounce counter

end if

if $is\\_swing^{t+1}$ and waiting for a rising edge then

Append $t+1$ to $rising\\_edge\\_list$

end if

if $not\text{ }is\\_swing^{t+1}$ and waiting for a falling edge and is
debounced then

Update step-specific features

Update $th_{dynamic}$ & $th_{static}$

Append $t+1$ to $falling\\_edge\\_list$

end if

Examples of the algorithm performance are shown in Figure 2. Once the
stance/swing phases are detected, we applied the algorithm described in [16]
by adapting the code from xioTechnologies/Gait-Tracking-With-x-IMU. The full
implementation is provided in the Appendix. We conducted a validation study
for the stride length estimation algorithm with two healthy adult participants
using Cometa System IMUs and the Vicon motion capture system. The validation
study is divided into both straight-line walking and circle walking due to the
limited size of the Vicon rig. Both walking patterns are important as our
planned path for the experiment requires both motions, with the circle walking
representing turns around the corners of the room. The percent error and
standard deviation (STD) for straight-line walking is -0.09$\pm$0.03 and the
error for circle-walking is -0.024$\pm$0.19 meters.

Figure 2: The gyroscope data in the x-axis from the sensor located on the
dominant leg of 3 participants during the experiment. The walking path
contains both straight lines and turns. The orange dot indicates the start of
the swing phase, and the green x indicates the end. The start detection is
consistent, but the end-of-swing can sometimes be premature (as shown in the
third sub-figure, where x is labelled when the foot is yet to become
stationary). This is consistent with our Vicon validation described in Section
II-A1, where the STD is larger during turns compared to straight-line walking.

####  II-A2 Model cue influence on gait

A sparse multi-output Gaussian Process (MOGP) is used to model the change in
gait parameters (i.e. cadence and stride length) as a result of a given
auditory cue. The model takes the form of
$f(x):\mathds{R}^{D}\rightarrow\mathds{R}^{P}$, where D is the dimension of
the input and P is the dimension of the output.

$\textbf{Y}=f(\textbf{x})=\mathrm{W}\textbf{g}(\textbf{x}),$ (1)

$\textbf{g}(\textbf{x})$ is a collection of Q independent GPs, where Q is the
number of latent GPs:

$\textbf{g}(\textbf{x})=\\{g_{q}(\textbf{x})\\}_{q=1}^{Q},g_{q}(\cdot)\sim\mathcal{GP}(0,k_{q}(\cdot,\cdot^{\prime}))$
(2)

The outputs are assumed to be linearly correlated through $\mathrm{W}$, known
as the Linear Model of Coregionalization (LMC) following the implementation
specified in [17]. The outputs of the MOGP are the estimated cadences and
stride lengths, while the inputs are the specified cues at the preceding time
step:

$\displaystyle\textbf{Y}=\begin{bmatrix}\hat{f}_{1},\hat{\ell}_{1}\\\
\hat{f}_{2},\hat{\ell}_{2}\\\ \vdots\\\
\hat{f}_{N},\hat{\ell}_{N}\end{bmatrix}$
$\displaystyle\textbf{x}=\begin{bmatrix}0\\\ c_{1}\\\ \vdots\\\
c_{N-1}\end{bmatrix}$

$\hat{f}_{n}$ is the estimated cadence and $\hat{\ell}_{n}$ is the estimated
stride length at the $n^{th}$ step from the gait measurement sub-system.
$c_{n-1}$ is the cue given at the previous step that results in the $n^{th}$
cadence/stride length. n is incremented at every footstep and
$n=[1,2,\ldots,N]$. $n=1$ represents the baseline cadence and stride length
when no cue is given.

A challenge associated with MOGP is the computation complexity associated with
the covariance matrix manipulation, which grows cubically with respect to the
amount of data. [18] has proposed using variational free energy approximation
combined with inducing points to construct a sparse approximation that reduces
the computation cost. The result is implemented in a python library (GPFlow)
[17], which is utilized in this study. Specifically, sparsity is introduced to
the MOGP through inducing points,
$\boldsymbol{\mathrm{Z}}=[z_{1},z_{2},...z_{M}]$. Then, the MOGP prior,
$p_{0}$, can be written in terms of $\boldsymbol{\mathrm{Z}}$, where

$p_{0}({\textbf{g}_{q}})=\mathcal{N}(m_{q}(\textbf{Z}),k_{q}(\textbf{Z},\textbf{Z}^{\prime}))$
(3)

The key model parameters are chosen as the following: $P=Q=2,D=1,M=20$. The
covariance, $k_{q}(\cdot,\cdot^{\prime})$, is chosen to be the sum of a
squared exponential kernel and a constant kernel, which allows possible higher
order SLCrel to be captured. To use the model to predict change in stride
length and cadence as a result of the input cues, the model is evaluated at
the new input location following Eq 4.

$Y^{\star}=Wg(x^{\star})\text{,}\quad x^{\star}=[c^{\star}_{n}]\text{,}\quad
Y^{\star}=[\hat{f}^{\star}_{n+1},\hat{\ell}^{\star}_{n+1}]$ (4)

####  II-A3 Cue Optimization

The cue-optimizing sub-system aims to provide cues that minimize the
difference between the predicted and desired gait states. The cost function
penalizes the squared difference between target cadence/stride length and
predicted cadence/stride length, as well as rapid cue changes.

$\displaystyle c_{opt}=\operatorname*{arg\,min}_{c^{\star}_{n}}J\mbox{,
subjected to }c_{min}\leq c^{\star}_{n}\leq c_{max}$ $\displaystyle
J(c^{\star}_{n})=\alpha_{f}(f_{target}-\hat{f}^{\star}_{n+1})^{2}+\alpha_{l}(\ell_{target}-\hat{\ell}^{\star}_{n+1})^{2}$
$\displaystyle+\alpha_{e}(c^{\star}_{n}-c_{n-1})^{2}$ (5)

In Eq 5, $c_{opt}$ is the cue to provide at the $n+1^{th}$ step constrained
between $c_{min}=0.65f_{baseline}$ and $c_{max}=1.35f_{baseline}$. The range
is determined empirically based on a previous study [7].
$\alpha_{f},\alpha_{l},\text{and }\alpha_{e}$ are three scaling factors that
weigh the relative importance of each cost term, which are initialized to 1.5,
10, and 0.05 respectively. $\hat{f}^{\star}_{n+1}$ is the predicted (i.e.
$n+1$ step) cadence and $\hat{\ell}^{\star}_{n+1}$ is the predicted stride
length estimated from the MOGP given the cue at the current step,
$c_{n}^{\star}$, using Eq 4. The cost function is solved using the Nelder-Mead
method in SciPy [19].

###  II-B Target Selection

$f_{target}$ and $\ell_{target}$ in Eq 5 are selected based on the
participant’s baseline cadence ($f_{baseline}$) and initial SLCrel measured at
the start of the experiment. $f_{baseline}$ is measured in a 6-Minute Walk
Test (6MWT) and the SLCrel is measured by providing the participants with 5
training beats at 1.16, 1.41, 1.58, 1.75, 1.91 Hz in a random order (values
adopted from [1]). 50 beats are provided for each frequency. A quadratic and a
linear polynomial is fitted to the training data using NumPy [20] and the
polynomial with a lower residual becomes the SLCrel. An example of SLCrel is
shown in Figure 3. $\ell_{target}$ is selected to be a 0.1 m increase from the
SLCrel, which is based on the error of the gait estimation algorithm. Two
candidate targets are evaluated by computing the y-values at $\pm
10\%f_{baseline}$ on the SLCrel and adding a 0.1 offset. The exact target is
chosen by looking at the two candidates $\ell_{target}$ and the higher value
is chosen. $f_{target}$ is then selected (i.e. the x value of $\ell_{target}$
on the SLCrel).

Figure 3: Example of the initial SLCrel. The dots represent the stride
length/cadence data collected during the training beats (labelled from T-1 to
T-5 from slow to fast). The participant exhibits a negative parabolic SLCrel
and $f_{target}\&\ell_{target}$ are chosen to be the location of the lighter
orange star labelled “Target Up”.

###  II-C Experimental Conditions

We compare the performance of two cueing strategies in two scenarios, leading
to 4 experimental conditions. Each condition lasts for 4 minutes. Since
healthy participants do not experience gait impairments, we evaluate the
performance of the framework in terms of its ability to change people’s stride
length. The two cueing strategies are the fixed and the adaptive strategy. The
fixed strategy delivers cues directly at $f_{target}$ and the adaptive
strategy provides cues using the HIL framework. We initialize the MOGP using
the data from the initial SLCrel. The two scenarios are either with or without
a secondary task. For the secondary task, participants perform a word reciting
task (i.e. reciting as many words beginning with a given letter). A set of
letters (S, P, C, and A), are randomly selected before the experiment and
randomly assigned. Conditions with secondary task are designed to emulate
natural daily living where people could be preoccupied with other tasks while
walking.

###  II-D Participants

We recruited 6 healthy adults (5M/1F, Age $27.5\pm 3.78$ years; Height
$172.17\pm 6.4$ (cm); Weight $71.67\pm 8.11$ (kg); mean$\pm$standard
deviation). We started the experiment with three participants (Group 1) who
only received 1 training session (described below) and the cue-triggering
conditions are described in Eq 6 & 7 over a 5-step window ($n_{window}$):

$\dfrac{\sum^{N}_{n=N-4}\hat{\ell}_{n}}{n_{window}}<\ell_{target}$ (6) $\text{
or
}\dfrac{\dfrac{\sum^{N}_{n=N-4}\hat{f}_{n}}{n_{window}}-f_{target}}{f_{target}}\leq
5\%$ (7)

We relaxed the cue-triggering condition for the next three participants (Group
2) to use only Eq 6 (see Section IV for relevant discussion).

###  II-E Protocol

Participants watched an introduction video and signed the consent form at the
start of the experiment. After putting on the IMUs, participants were given
the first training session where a metronome beat is randomly selected by the
experimenter and participants practice syncing their walking to the metronome
beat. The training takes less than one minute. Participants walked around a
room, with the longest straight edge being 15 meters. The walking path
contained both straight-line walking and 4 corner turns. Participants were
free to choose the direction (clockwise or counter-clockwise) of their walk
and kept to the same direction throughout. After the training session,
participants were told to walk at their natural pace for the 6MWT. After the
6MWT, participants filled out a demographic survey. The initial SLCrel is then
constructed (see Section II-B). Participants were told to sync their walking
to the metronome beat for each condition.

For the first three participants (Group 1), the next part of the experiment
involved the 4 experimental conditions described in Section II-C, which were
selected randomly and blinded from the participants. Participants filled out a
survey plus the NASA Task Load Index (TLX) after each condition.

For the next three participants (Group 2), a second training session, which
takes approximately one minute, was provided before the experimental
conditions. In the training, the experimenter first played another randomly
selected metronome beat and walked with the participant. After a few steps of
syncing to the beat, the experimenter asked the participant to “take bigger
steps” while keeping to the same beat. The experimenter then asked the
participants to “take smaller steps” while keeping to the same beat. The
participants were told that the training aims to demonstrate how various step
lengths can be associated with a beat. Participants were then asked to try and
figure out the intention of the framework during the experiment in terms of
how fast and how far the metronome wanted them to step. They would know they
have it correct when the beats turn off, and the goal was to keep the beats
off.

Participants in both groups were told they will be evaluated based on their
gait performance and the number of words they can recite if the secondary task
is present. All participants concluded the experiment after an interview
during which the participant reviewed their own data and the experimenter
informed the participants of the cueing strategies. The study (ID 34903) was
approved by the Monash University Human Research Ethics Committee.

###  II-F Materials

The IMU sensors from the WaveTrack Inertial System are sampled at 142 Hz
(Cometa Systems, Milan, IT) and streamed wirelessly into a custom Python
program. The program runs on a laptop (Windows 10, i7 core with no GPU), which
plays auditory cues from a speaker (Phillips BT50A). Two sensors are used; one
on each foot. The sensor is fixed to the flat part of the foot, which is
identified by asking participants to lift their heels; the sensor is then
placed on top of the folding crease and secured using duct tape. The sensor is
oriented such that the x-y plane of the sensor is parallel to the transverse
plane of the body. The sensor’s y-axis points in the sagittal plane facing
forward and z-axis points towards the head.

###  II-G Analysis

No statistical analysis was conducted due to the small sample size. Here we
focus on the main gait metric (stride length) and participants’ subjective
ratings.

##  III RESULTS

This feasibility study aims to determine whether participants are able to
increase their stride length using auditory cues. We calculate the delta
stride length, which is the mean difference between the participant’s stride
length during a condition compared to the mean of their baseline stride length
during the 6MWT. The result is shown in Figure 4. Data in Figure 4(I)-A
indicate that participants from Group 1 are not changing their strides even
during the condition without the secondary task. Without sufficient
information, the cue is delivered inefficiently as it is played almost 100% of
the time without being able to influence the participant’s gait, as shown in
Figure 4(II)-A&C. Despite the lack of instructions, the adaptive condition
(A-1) naturally encourages participants to explore a variety of step lengths
through the change in cues (as evidenced by the larger variance in the data)
as seen in Figure 4(I)-A. With more exploration, participants had a higher
chance of meeting the cue-triggering conditions described in Eq 7 & Eq 6,
thereby turning the metronome off (i.e. Figure 4(II)-A, where the lines
between F1 and A1 trends downwards, favouring the adaptive approach). When the
secondary task is added without sufficient instruction, further reduction in
step length is observed (Figure 4(I)-C$<$A). However, the adaptive condition
still encouraged more variations in step length, leading to a closer-to-
baseline median (seen in Figure 4(I)-C, where two participants trends upwards
between F-1 and A-1, favouring the adaptive approach. One participant has a
slight reduction).

Figure 4: The figure displays two outcome metrics of the study. (I) shows the
change in stride length compared to baseline stride length. We want the metric
to be as high as possible (i.e. longer steps). (II) shows the percentage of
time the cue is on during the 4-minute experiment. The goal is for the percent
on time to be low. The connected lines between two columns show how the
individual’s data changed between the fixed and adaptive approaches. The two
left panels (A) & (B) are the conditions without secondary task and (C) & (D)
are with the task. F refers to the fixed cueing strategy and A refers to the
adaptive strategy. The 1 in the x-axis denotes the groups. Group 1 received no
additional training and is subjected to both $f_{target}\&\ell_{target}$.
Group 2 received 2 training sessions and only had the $\ell_{target}$ active
for cue-triggering.

Once the instructions are modified for Group 2, participants started changing
their stride length, as evident by the positive increase in step length in
Figure 4(I)-B. A larger change in step length in the fixed approach than in
the adaptive approach is observed in the conditions without secondary task
(lines trend downward in Figure 4(I)-B between F-2 and A-2, favouring the
fixed condition). This could be due to participants varying their step lengths
when beats at a new pace are provided, which lowers the overall change in step
length. Overall, the stride length decreases in the presence of the secondary
task (Figure 4(I)-B$>$D). The median percent on time is lower without
secondary task (Figure 4(II)-B$<$D). When the secondary task is added, two
participants experienced a decrease in percent on time compared to the fixed
approach and one increased drastically (Figure 4(II)-D).

The initial results first suggest that without explicit association between
stride length and cues (Group 1), the adaptive approach is more effective in
changing people’s stride length (as most lines trend upwards between fixed and
adaptive in Figure 4(I)-A&C) reducing the percent on time (as most lines trend
downwards between fixed and adaptive in Figure 4(II)-A&C). When the second
training session is added (Group 2), the results suggest there could be two
ways of responding to the adaptive approach. For some participants, the
adaptive approach continues to improve stride length and reduces percent on
time, while others are confused by the non-static nature of the cue. This is
supported by the post-condition questionnaires. When asked if and how the
participants felt their gait changing, Group 2 answered that their gait is
“random” more often than Group 1. This suggests that participants in Group 2
are consciously exploring the variations in stride length, but may still be
difficult for them to “figure out” the intention of the framework as per
instruction. This is also supported by the Task Load Index (TLX) score
questions, where the largest and second largest change is seen in the
participant’s stress/irritation level (i.e. frustrated about not being able to
turn off the metronome) followed by the physical demand of the task (i.e.
exploring more step lengths). Overall, TLX increased between Group 1 and Group
2 (16.58$\pm$7.12 for Group 1 and 18.18$\pm$6.22 for Group 2;
mean$\pm$standard deviation).

##  IV DISCUSSION

In this study, we demonstrate that it is possible to change people’s stride
length using auditory cues given sufficient instructions. This aligns with how
cues are used during rehabilitation by bringing attention to the walking task.
For Parkinson’s, the attentional mechanism helps bypass the defective
automatic control due to the disease, thereby improving their walking [2]. In
the modified instruction (i.e. with Group 2), we emphasize attention control,
which resulted in a greater change in stride length and higher TLX scores. In
addition to the instruction, the cue-triggering conditions described in Eq 6
and 7 could also contribute to participants’ lack of stride changes. This is
because the $\ell_{target}$ that is selected is not part of the natural
SLCrel, and therefore satisfying both conditions may not be feasible. Finally,
since $f_{target}$ can easily be satisfied (as a participant put it: “[I]
simply match the pace with the metronome”), a change in stride length in order
to keep the metronome off was difficult to realize due to the natural
association between walking frequency and metronome frequency. Therefore, the
demonstration session was necessary to highlight the connection between
metronome frequency and stride length.

The initial results for Group 2 suggest that the fixed approach performs
better without secondary task, but the adaptive approach is better when the
secondary task is added, given the reduction in percent on time. In addition,
participants mentioned that the adaptive approach in general is more
attention-demanding compared to the fixed approach. From these results, we
plan to expand the study to include people with Parkinson’s as well as a
control group of older adults to evaluate the performance of the cueing
strategies in relation to the SLCrel.

## APPENDIX

The full implementation of the gait detection algorithm and instructions on
parameter tuning can be found here: https://doi.org/10.26180/c.6619669.v3.

## References

  * [1] T. Egerton, M. Danoudis, F. Huxham, and R. Iansek, “Central gait control mechanisms and the stride length–cadence relationship,” _Gait & posture_, vol. 34, no. 2, pp. 178–182, 2011.
  * [2] D. Sweeney, L. R. Quinlan, P. Browne, M. Richardson, P. Meskell, and G. ÓLaighin, “A technological review of wearable cueing devices addressing freezing of gait in parkinson’s disease,” _Sensors_ , vol. 19, no. 6, p. 1277, 2019.
  * [3] M. Bächlin, M. Plotnik, D. Roggen, N. Giladi, J. M. Hausdorff, and G. Tröster, “A wearable system to assist walking of parkinson s disease patients,” _Methods of information in medicine_ , vol. 49, no. 01, pp. 88–95, 2010.
  * [4] V. Mikos, C.-H. Heng, A. Tay, S.-C. Yen, N. S. Y. Chia, K. M. L. Koh, D. M. L. Tan, and W. L. Au, “A wearable, patient-adaptive freezing of gait detection system for biofeedback cueing in parkinson’s disease,” _IEEE transactions on biomedical circuits and systems_ , vol. 13, no. 3, pp. 503–515, 2019.
  * [5] R. S. Schaefer, “Auditory rhythmic cueing in movement rehabilitation: findings and possible mechanisms,” _Philosophical Transactions of the Royal Society B: Biological Sciences_ , vol. 369, no. 1658, p. 20130402, 2014.
  * [6] P. Ginis, E. Nackaerts, A. Nieuwboer, and E. Heremans, “Cueing for people with parkinson’s disease with freezing of gait: a narrative review of the state-of-the-art and novel perspectives,” _Annals of physical and rehabilitation medicine_ , vol. 61, no. 6, pp. 407–413, 2018.
  * [7] T. L. Wu, A. Murphy, C. Chen, and D. Kulić, “Human-in-the-loop auditory cueing strategy for gait modification,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 3521–3528, 2021.
  * [8] T. L. Wu, A. Murphy, C. Chen, and D. Kulić, “Adaptive cueing strategy for gait modification: A case study using auditory cues,” _Frontiers in Neurorobotics_ , 2023.
  * [9] H. Zhang, Y. Yin, Z. Chen, Y. Zhang, A. K. Rao, Y. Guo, and D. Zanotto, “Wearable biofeedback system to induce desired walking speed in overground gait training,” _Sensors_ , vol. 20, no. 14, p. 4002, 2020.
  * [10] H. Zhang, S. Li, Q. Zhao, A. K. Rao, Y. Guo, and D. Zanotto, “Reinforcement learning-based adaptive biofeedback engine for overground walking speed training,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 3, pp. 8487–8494, 2022.
  * [11] S. J. Spaulding, B. Barber, M. Colby, B. Cormack, T. Mick, and M. E. Jenkins, “Cueing and gait improvement among people with parkinson’s disease: a meta-analysis,” _Archives of physical medicine and rehabilitation_ , vol. 94, no. 3, pp. 562–570, 2013.
  * [12] M. Suteerawattananon, G. Morris, B. Etnyre, J. Jankovic, and E. Protas, “Effects of visual and auditory cues on gait in individuals with parkinson’s disease,” _Journal of the neurological sciences_ , vol. 219, no. 1-2, pp. 63–69, 2004.
  * [13] I. Skog, P. Handel, J.-O. Nilsson, and J. Rantakokko, “Zero-velocity detection—an algorithm evaluation,” _IEEE transactions on biomedical engineering_ , vol. 57, no. 11, pp. 2657–2666, 2010.
  * [14] L. Van Nguyen and H. M. La, “Real-time human foot motion localization algorithm with dynamic speed,” _IEEE Transactions on Human-Machine Systems_ , vol. 46, no. 6, pp. 822–833, 2016.
  * [15] M. Mancini, K. Smulders, G. Harker, S. Stuart, and J. G. Nutt, “Assessment of the ability of open-and closed-loop cueing to improve turning and freezing in people with parkinson’s disease,” _Scientific reports_ , vol. 8, no. 1, pp. 1–9, 2018.
  * [16] S. Madgwick _et al._ , “An efficient orientation filter for inertial and inertial/magnetic sensor arrays,” _Report x-io and University of Bristol (UK)_ , vol. 25, pp. 113–118, 2010.
  * [17] M. van der Wilk, V. Dutordoir, S. John, A. Artemev, V. Adam, and J. Hensman, “A framework for interdomain and multioutput gaussian processes,” _arXiv preprint arXiv:2003.01115_ , 2020.
  * [18] M. Álvarez, D. Luengo, M. Titsias, and N. D. Lawrence, “Efficient multioutput gaussian processes through variational inducing kernels,” in _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_. JMLR Workshop and Conference Proceedings, 2010, pp. 25–32.
  * [19] 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.
  * [20] M. Schwartze, P. E. Keller, A. D. Patel, and S. A. Kotz, “The impact of basal ganglia lesions on sensorimotor synchronization, spontaneous motor tempo, and the detection of tempo changes,” _Behavioural brain research_ , vol. 216, no. 2, pp. 685–691, 2011.


# Shortcuts to Quantum Approximate Optimization Algorithm

Yahui Chai<EMAIL_ADDRESS>Origin Quantum Computing Company Limited, Hefei
230026, China  Yong-Jian Han  CAS Key Laboratory of Quantum Information
(University of Science and Technology of China), Hefei 230026, China  Yu-Chun
Wu  CAS Key Laboratory of Quantum Information (University of Science and
Technology of China), Hefei 230026, China  Ye Li  Origin Quantum Computing
Company Limited, Hefei 230026, China  Menghan Dou  Origin Quantum Computing
Company Limited, Hefei 230026, China  Guo-Ping Guo<EMAIL_ADDRESS>Origin
Quantum Computing Company Limited, Hefei 230026, China  CAS Key Laboratory of
Quantum Information (University of Science and Technology of China), Hefei
230026, China

###### Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical
hybrid algorithm intending to find the ground state of a target Hamiltonian.
Theoretically, QAOA can obtain the approximate solution if the quantum circuit
is deep enough. Actually, the performance of QAOA decreases practically if the
quantum circuit is deep since near-term devices are not noise-free and the
errors caused by noise accumulate as the quantum circuit increases. In order
to reduce the depth of quantum circuits, we propose a new ansatz dubbed as
“Shortcuts to QAOA” (S-QAOA), S-QAOA provides shortcuts to the ground state of
target Hamiltonian by including more two-body interactions and releasing the
parameter freedoms. To be specific, besides the existing ZZ interaction in the
QAOA ansatz, other two-body interactions are introduced in the S-QAOA ansatz
such that the approximate solutions could be obtained with smaller circuit
depth. Considering the MaxCut problem and Sherrington-Kirkpatrick (SK) model,
numerically computation shows the YY interaction has the best performance. The
reason for this might arise from the counterdiabatic effect generated by YY
interaction. On top of this, we release the freedom of parameters of two-body
interactions, which a priori do not necessarily have to be fully identical,
and numerical results show that it is worth paying the extra cost of having
more parameter freedom since one has a greater improvement on success rate.

##  I Introduction

In the noisy intermediate-scale quantum (NISQ) era [1], the number of reliable
quantum operations is limited by the quantum errors which contains quantum
decoherence, rotation error, and so on. Thus people are interested in the
quantum-classical hybrid algorithm whose quantum circuit depth is decreased
with the help of classical optimizers, like the Quantum Approximate
Optimization Algorithm (QAOA) [2] which is expected to get an approximate
solution for combinatorial optimization problems. In this hybrid algorithm,
the quantum state is prepared by a quantum computer, the parameters in the
quantum circuit are optimized by a classical optimizer to find an evolution
path that needs less circuit depth. Furthermore, QAOA is expected to have a
better performance than quantum adiabatic algorithms (QAA) and get a quantum
advantage using near-term devices [3, 4]. However, the performance of QAOA is
limited by the noise of the near-term devices [5], and Google’s experiment for
QAOA with their Sycamore superconducting qubit quantum processor shows that
errors overwhelm the theoretical performance increase at larger layers [6].
Therefore executing QAOA on near-term quantum computers is a challenging task.
It is important to reduce the circuit depth of QAOA to make it achievable for
near-term devices.

QAOA can be regarded as a digitized and variational version of QAA. QAA starts
with a simple-to-prepared ground state of an initial Hamiltonian, and the
adiabatic theorem guarantees that the ground state of the final Hamiltonian
can be obtained if the time-dependent Hamiltonian varies slowly. The adiabatic
condition requires that the running time of QAA scales as $T\sim
O(1/{\Delta_{min}}^{2})$, $\Delta_{min}$ is the minimal spectral gap [7] of
the quantum system during the evolution, thus many problems are hard to
optimize using QAA because of the overlong annealing time. Besides, the
digitization of QAA may lead to a deep quantum circuit to minimize the trotter
error [8, 9]. QAOA is expected to overcome these problems by optimizing
parameters (including evolution path and duration for every digitized step)
using a classical optimizer. The optimized parameters of QAOA are related to a
fast evolution path, so QAOA is expected to break through the limits of the
adiabatic condition [3].

Shortcuts to adiabaticity (STA) [10, 11] is a class of methods to accelerate
the quantum adiabatic process, counterdiabatic (CD) driving [12, 13, 14] is a
technique of STA to reduce the finite-speed diabatic effect by adding counter
terms to the time-dependent Hamiltonian. The CD driving Hamiltonian has a
better performance and reduces the evolution time compared to adiabatic
evolution [15]. Besides, Ref. [16] proposes a superadiabatic route to
implement universal quantum computation by using CD driving, and energy cost
of STA via CD driving is studied at Ref. [16, 17]. In addition, energy cost
optimization of CD driving, through the correct choice of the counterdiabatic
Hamiltonian is studied in Ref. [18]. Recently, Ref. [4] indicates QAOA is at
least counterdiabatic and has a better performance than finite time adiabatic
evolution. There is also an effort to add a conterdiabatic term to the ansatz
of QAOA to reduce the quantum circuit depth [19, 20].

Our work focuses on the MaxCut problems and Sherrington-Kirkpatrick (SK)
Model, both of them are NP-hard problems, and the QAOA is expected to have a
quantum acceleration on these problems. In this work, we investigate the
counterdiabatic effect of QAOA, and the simulation result implies that adding
a two-gate term associate with the YY interaction to the quantum circuit will
accelerate the optimization of QAOA. Besides, we release the QAOA parameter
freedom of the two-body interactions (including ZZ interaction and YY
interaction) to reduce the quantum circuit depth, eg. each two-body
interaction has its independent parameter. The idea of extending the parameter
degree is mentioned in 2017 [21] and they use random initial parameters of
each ZZ interaction. In our case, firstly, we optimize the QAOA parameters to
get an optimal global value, and then use the optimal parameters of QAOA as
the initial parameters of each two-body term to do a further local
optimization. The proposed algorithm uses the philosophy of STA, so we call it
“Shortcuts to QAOA” (S-QAOA), and the simulated result shows that S-QAOA can
get a good result with a shallower quantum circuit compared with QAOA.

##  II Problems and Quantum Algorithms

In this work, we focus on the MaxCut problem and SK model. The MaxCut problem
is defined on a graph $G(V,E)$, $V=\\{1,2,\cdots,n\\}$ is the set of vertices,
and $E=\\{\left((i,j),w_{ij}\right)\\}$ is the set of edges where $(i,j)$ is a
pair of connected vertices and $w_{ij}$ is the weight of the edge $(i,j)$. We
study two classes of graphs: the first class is unweighted 3-regular graphs
(u3R) whose weights $w_{ij}$ are a constant for the all edges, eg.
$w_{ij}=1,\forall(i,j)\in E$; the second class is weighted 3-regular graphs
(w3R) whose weights $w_{ij}$ are uniform random numbers in range $[0,1]$. The
target Hamiltonian of MaxCut problem is:

$H_{C}=-\sum_{(i,j)\in E}w_{ij}\frac{I-Z_{i}Z_{j}}{2}.$ (1)

The SK model is defined on the complete graph and the coefficient $w_{ij}$ is
randomly chosen from the set $\\{-1,1\\}$. The Hamiltonian of the SK model is
:

$H_{C}=\sum_{i<j}w_{ij}Z_{i}Z_{j}.$ (2)

###  II.1  Quantum Adiabatic Algorithms

QAA is able to find the ground state of a target Hamiltonian if the annealing
process is slow enough, and its feasibility is guaranteed by the adiabatic
theorem. In QAA, a simple-to-prepared quantum state is chosen as the initial
state, which usually is the uniform superposition over computational basis
states: $\psi(t=0)=|+\rangle^{\otimes n}$, $n$ is the number of qubits of the
quantum system. $\psi(t=0)$ is the ground state of Hamiltonian
$H_{B}=-\sum_{i=1}^{n}X_{i}$. The time-dependent Hamiltonian of QAA is:

$\displaystyle H(t)=(1-\lambda(t))H_{B}+\lambda(t)H_{C},$ (3) $\displaystyle
0\leq t\leq T,\lambda(0)=0,\lambda(T)=1,$

where $H_{C}$ represents the target Hamiltonian. The time evolved state driven
by $H$ would be:

$|\psi(T)\rangle=\mathcal{T}e^{-i\int_{0}^{T}dtH(t)}|\psi(0)\rangle,$ (4)

where $\hbar=1$ and $\mathcal{T}$ is the time-ordering operator. The
approximate ground state of $H_{C}$ can be obtained in the end $t=T$ if the
Hamiltonian $H$ varies adiabatically.

STA is able to suppress the finite-speed diabatic excitations by adding the CD
driving term to the Hamiltonian $H$ [14], this CD term is theoretically known
and given by adiabatic gauge potential (AGP) $A_{\lambda}$ [22]:

$H_{CD}(t)=H+\dot{\lambda}A_{\lambda}.$ (5)

However, it requires the knowledge of the spectral properties of the
instantaneous Hamiltonian to get the AGP, and the exact AGP is typically
nonlocal, which makes the experimental implementation difficult [23]. The
exact AGP can be approximated by a local parameterized gauge potential
$A_{\lambda}(\bm{\alpha})$, and the requirement of $A_{\lambda}(\bm{\alpha})$
is to minimize the action $S(A_{\lambda})$:

$\displaystyle\mathop{Min}\limits_{\bm{\alpha}}$
$\displaystyle:S\left(A_{\lambda}(\bm{\alpha})\right)=Tr\left[G^{2}(A_{\lambda})\right],$
(6) $\displaystyle
G(A_{\lambda})=\partial_{\lambda}A_{\lambda}+i[A_{\lambda},H],$

the coefficient $\bm{\alpha}$ can be determined variationally [24].
Furthermore, the approximate AGP can be systematically constructed by the
nested commutators [25]:

$A_{\lambda}^{l}(\bm{\alpha})=i\sum_{k=1}^{l}\alpha_{k}(t)\underbrace{[H,[H,\cdots[H,}_{2k-1}\partial_{\lambda}H]]].$
(7)

The first order of the approximate AGP is the commutator of the initial
Hamiltonian $H_{B}$ and the target Hamiltonian $H_{C}$, so the counterdiabatic
Hamiltonian becomes:

$\displaystyle H_{CD}^{1}$ $\displaystyle=H+\dot{\lambda}A_{\lambda}^{1}$ (8)
$\displaystyle=(1-\lambda(t))H_{B}+\lambda(t)H_{C}+i\dot{\lambda}\alpha_{1}[H_{B},H_{C}],$

and it can be proven that the coefficient $\alpha_{1}$ is negative [4]. In
$l=+\infty$ limits, the CD driving terms $A_{\lambda}^{l}(\bm{\alpha})$ are
able to compensate the diabatic excitations exactly, but it is necessary to
just consider the first few orders of $A_{\lambda}^{l}(\bm{\alpha})$ to avoid
the nonlocal operations.

###  II.2 Quantum Approximate Optimization Algorithm

The ansatz of QAOA consists of a series of digitized evolution, and the
parameters of QAOA are optimized by a classical optimizer [2]:

$|\psi(\bm{\beta},\bm{\gamma})\rangle=e^{-i\beta_{p}H_{B}}e^{-i\gamma_{p}H_{C}}\cdots
e^{-i\beta_{1}H_{B}}e^{-i\gamma_{1}H_{C}}|\psi(0)\rangle.$ (9)

The purpose of the classical optimization is to find the optimal parameters to
minimize the expectation of the target Hamiltonian:

$\displaystyle\mathop{Min}\limits_{\bm{\beta},\bm{\gamma}}$
$\displaystyle:E(\bm{\beta},\bm{\gamma})=\langle\psi(\bm{\beta},\bm{\gamma})|H_{C}|\psi(\bm{\beta},\bm{\gamma})\rangle,$
(10)
$\displaystyle\bm{\beta}=(\beta_{1},\cdots,\beta_{p}),\bm{\gamma}=(\gamma_{1},\cdots,\gamma_{p}).$

If the layer $p$ of QAOA is large enough, the expectation $E$ will decrease
during the optimization and converge to the target Hamiltonian ground state.
The effective Hamiltonian of QAOA can be constructed by the second order
Baker-Campbell-Hausdorff (BCH) expansion [4]:

$\displaystyle e^{-i\beta_{k}H_{B}}e^{-i\gamma_{k}H_{C}}\sim e^{-iH_{eff}},\
1\leq k\leq p,$ (11) $\displaystyle
H_{eff}=\gamma_{k}H_{C}+\beta_{k}H_{B}-\frac{i\beta_{k}\gamma_{k}}{2}[H_{B},H_{C}]$

Compare the result of Eq.8 and Eq.11, we can find that the effective
Hamiltonian $H_{eff}$ of QAOA has a first-order CD driving term, and the
coefficient of this term is also negative. So the evolution of QAOA will
include some counterdiabatic effects to compensate the diabatic excitation.

###  II.3 Shortcuts to QAOA

Inspired by the technique of STA, we consider the counterdiabatic effect of
QAOA by introducing more two-body interactions: $H_{M}=\sum\limits_{(i,j)\in
E}\frac{P_{i}Q_{j}+Q_{i}P_{j}}{2},PQ\in\\{YZ,YY,XX,XZ,XY\\}$. The ansatz and
the effective Hamiltonian become:

$\displaystyle
e^{-i\alpha_{k}H_{M}}e^{-i\beta_{k}H_{B}}e^{-i\gamma_{k}H_{C}}\sim
e^{-iH_{eff}},\ 1\leq k\leq p,$ (12) $\displaystyle H_{eff}=\alpha H_{M}+\beta
H_{B}+\gamma H_{C}$
$\displaystyle-i\frac{\beta\gamma}{2}[H_{B},H_{C}]-i\frac{\alpha\beta}{2}[H_{M},H_{B}]-i\frac{\alpha\gamma}{2}[H_{M},H_{C}],$

where $\alpha_{k},k=1,\cdots,p$ are the variational parameters for $H_{M}$.
The effective Hamiltonian in Eq.12 might have more CD terms and would
accelerate the process of quantum optimization. Introducing more interactions
led to a deeper quantum circuit, this problem can be partially solved by a
compact implementation of the $H_{M}$ and $H_{C}$ (Eq.13), which does not need
extra SWAP gates if using a local connectivity superconducting quantum
computer. Furthermore, the combination of YY/XX and ZZ interaction can be
realized using two CNOT gates and some single-qubit gates, which has the same
number of CNOT gates as the way only implementing ZZ interaction (the details
of this part will be discussed in Sec.IV). In this case, the circuit depth of
S-QAOA and QAOA can be regarded as the same, because the errors caused by CNOT
gates are more serious than single-qubit gates.

Another difference between S-QAOA and QAOA is the optimization of the
parameters: in S-QAOA, after the optimization of QAOA parameters, the
parameter freedoms of two-body interactions are released and a further
optimization is performed. More parameters will improve the expressivity of
the quantum circuit and can get a better result than QAOA in the same quantum
layer. The procedure of S-QAOA is as follows:

1\. Optimize the QAOA parameters using INTERP strategy [3], get the optimal
parameters $(\tilde{\bm{\beta}},\tilde{\bm{\gamma}})_{p}$ for layer $p$.

2\. Release the parameter freedom of $ZZ$ interaction, and introduce an extra
two-body interaction
$M_{ij}=\frac{P_{i}Q_{j}+Q_{i}P_{j}}{2},PQ\in\\{YZ,YY,XX,XZ,XY\\}$, followed
by each $ZZ$ interaction. Operation of each layer $k\in[1,p]$ of S-QAOA is:

$\displaystyle
e^{i\beta_{k}\sum\limits_{i}^{n}X_{i}}e^{-i\gamma_{k}\sum\limits_{ij}w_{ij}Z_{i}Z_{j}}\rightarrow$
(13) $\displaystyle
e^{i\beta_{k}\sum\limits_{i}^{n}X_{i}}\prod\limits_{ij}\\{e^{-i\gamma^{ij}_{k}w_{ij}Z_{i}Z_{j}}e^{-i\alpha_{k}\gamma^{ij}_{k}w_{ij}M_{ij}}\\}.$

The initial parameters of S-QAOA are:
$\beta_{k}=\tilde{\beta}_{k},\gamma_{k}^{ij}=\tilde{\gamma}_{k},\alpha_{k}=0$.
The strength of $M_{ij}$ interaction should be positively related to that of
$Z_{i}Z_{j}$ interaction, so the parameter $\gamma_{ij}$ is added to each
$M_{ij}$ interaction (This is the ansatz of S-QAOA for SK model, and it is the
same for MaxCut problem except for a coeffecient $\frac{1}{2}$. For
simplicity, we will only show the ansatz for SK model in the following.)

3\. Use the finite-difference method to calculate the gradients of parameters
$(\\{\gamma^{ij}_{k}\\},\beta_{k},\alpha_{k})$:

$\displaystyle g(\theta)=\frac{E(\theta+\epsilon)-E(\theta)}{\epsilon},$ (14)
$\displaystyle\forall\theta\in(\\{\gamma^{ij}_{k}\\},\beta_{k},\alpha_{k}),k=1,\cdots,p,$

$\epsilon$ is a small constant. Set a threshold $\delta_{1}$ and if
$|g(\theta)|>\delta_{1}$, add $\theta$ to set $A$.

4\. Optimize the parameters in set $A$ until convergent, if the decrease of
energy is smaller than a threshold $\delta_{2}$ after the optimization, exit;
else, update the optimized parameters and return to step3.

##  III Simulation Result

We study the u3R and w3R MaxCut problem on 14-vertex graphs, and SK model on
6-vertex graphs. In each case, the results are averaged on 20 random graphs.
There are three ansatzes being studied: QAOA; only releasing the parameter
freedom of ZZ interaction (This ansatz only contains ZZ interaction, and for
simplicity, we call it ‘ZZ technique’ below); adding an extra two-body
interaction and releasing the freedom of parameters (S-QAOA). The simulation
result implies that the third ansatz has the best performance in all cases,
and the suitable extra two-gate term is able to accelerate the optimization
process significantly. A comprehensive study of the optimal type of extra two-
gate term in S-QAOA can be found in Fig.8, which shows the performance and the
comparison of all the possible extra two-gate types:
$M_{ij}=\frac{P_{i}Q_{j}+Q_{i}P_{j}}{2},PQ\in\\{YZ,YY,XX,XZ,XY\\}$. In
general, $YY$ interaction has the best performance, and it is included in
S-QAOA ansatz. Thus the operation of each layer $k\in[1,p]$ of S-QAOA is:

$e^{i\beta_{k}\sum\limits_{i}^{n}X_{i}}\prod_{ij}\\{e^{-i\gamma^{ij}_{k}w_{ij}Z_{i}Z_{j}}e^{-i\alpha_{k}\gamma^{ij}_{k}w_{ij}Y_{i}Y_{j}}\\}.$
(15)

Figure 1: Comparison of the performance of QAOA, $ZZ$ technique and S-QAOA for
MaxCut problem on 14-vertex u3R graphs. $(a)$The fractional error of the
results obtained by these algorithms, the definition of the fractional error
is : $r=1-\frac{E}{E_{opt}}$, $E_{opt}$ is the theoretical optimal value.
$(b)$The fidelity obtained by these algorithms, the fidelity represents the
possibility of the optimal solutions in the final state. Label ‘ZZ’ represents
the ansatz which only releases the freedom of parameters (ZZ technique). Label
‘YY’ represents the S-QAOA ansatz.

The results of u3R MaxCut problem are shown in Fig.1. Obviously, only
releasing the freedom of parameters of the existing $ZZ$ interaction will
produce a better result in the same layer than QAOA. On top of this, adding
the $YY$ interaction will improve the performance further, especially at the
low layer where the performance of QAOA is not so good. When the quantum layer
$p$ increases, the difference between the three ansatz is smaller, this is due
to that the evolution time is large enough for QAOA if the quantum layer is
large and there is little space for improvement. Fig.2 demonstrate the
simulation results of w3R graphs, and the superiority of S-QAOA is more
obvious in this case, the average fidelity is improved significantly even at
$p=10$. The MaxCut problem on w3R graphs is more difficult than u3R graphs,
since the energy gap of the MaxCut Hamiltonian on w3R graph is smaller than
that of u3R graph, and it needs a longer evolution time to satisfy the
adiabatic condition. The result shows the potential of S-QAOA to solve the
problems which are difficult for QAA and QAOA.

SK model is defined on the complete graph, it is challenging to implement SK
model on a NISQ device which has a limited qubit connectivity. Because of the
all-to-all interaction of SK model, all the nodes can be entangled together at
$p=1$, and there are sufficient parameters to optimize if the parameters of ZZ
interaction are independent. So that a pretty good result can be obtained at
$p=1$ if only releasing the parameter freedom (Fig.3). Furthermore, if a $YY$
interaction is added to the ansatz, the fidelity is obviously improved and
reaches about $80\%$ at $p=1$. S-QAOA introduces only one extra parameter
compared with the ZZ technique, and the performance of S-QAOA is significantly
better than the latter at $p=1$. The significant improvement produced by $YY$
interaction confirms its effects on countering the diabatic excitations and
accelerating the process of quantum optimization. The difference between
S-QAOA and $ZZ$ technique becomes smaller and smaller when the quantum layer
$p$ is increased, and this is due to that the parameter freedoms of $ZZ$
technique are enough for the optimization at large layer $p$, and there is not
much space for S-QAOA to improve.

Figure 2: Comparison of (a) the fractional error and (b) the fidelity of QAOA
, ZZ technique and S-QAOA for MaxCut problem on 14-vertex w3R graphs. The
performance of S-QAOA is obviously better than QAOA at the same layer. The
fidelity of S-QAOA in $p=4,5$ is rough twice as much as that of QAOA.
Moreover, if the quantum layer $p$ is increased, S-QAOA is still able to
improve the fidelity of the result. For example, S-QAOA gets a $38\%$
improvement of the fidelity over QAOA at $p=10$. Figure 3: Comparison of (a)
the fractional error and (b) the fidelity of QAOA, ZZ technique and S-QAOA for
6-vertex SK model. $ZZ$ technique can significantly decrease the fractional
error and improve the fidelity at low layers, and the result can be improved
further by using S-QAOA with a few additional parameters.

S-QAOA has a better performance in all cases we study, e.g. for a specific
quantum layer, $R_{p}=p_{S}/p_{Q}>1$, $p_{S}(p_{Q})$ is the possibility of the
optimal solution got by S-QAOA(QAOA). S-QAOA does a further optimization and
has more parameters compared with QAOA, so the number of function evaluations
of S-QAOA is more than that of QAOA, e.g. $R_{f}=f_{S}/f_{Q}>1$,
$f_{S}(f_{Q})$ is the cumulative number of function evaluations of
S-QAOA(QAOA), which will faithfully reflect the total cost of the algorithm.
More specifically, $f_{S}=f_{Q}+f_{G}+f_{O}$, where $f_{G}$ is the number of
function evaluations for calculating the gradients of parameters, and $f_{O}$
is the number of function evaluations for further optimizations in S-QAOA. It
is necessary to consider whether it is cost-effective to do these extra
optimizations. We show the ratio of $R_{f}$ and $R_{p}$: $R_{fp}=R_{f}/R_{p}$
in Fig.4, and $R_{fp}<1$ represents that it is deserved to do the extra
optimizations of S-QAOA to produce a higher improvement of fidelity. It is
clearly that the ratio $R_{fp}<1$ if $p\leq 4$ for almost cases. If p
increases, QAOA can produce quite high fidelity for SK model and u3R MaxCut
problem. There is little space to improve for S-QAOA, so the ratio $R_{fp}$ of
SK model and u3R MaxCut problem approach to 1 or even larger than 1 for large
p. For w3R MaxCut problem, the fidelity of QAOA is far away from 1, so S-QAOA
can improve the fidelity effectively with some further optimizations. In all,
S-QAOA is an effective way to improve the result of QAOA, especially in case
QAOA has limited performance.

Figure 4: The ratio of function evaluations and fidelity for u3R, w3R MaxCut
problems and SK model. We include 20 random instances for each problem. There
are some unusual data in w3R MaxCut case, and the reason is that the cost
function of S-QAOA is the expectation of the energy, so it is possible to get
a lower fidelity with a better expectation value. These unusual points
disappear when p increases.

##  IV Discussion

The quantum circuit of QAOA consists of the alternating implementation of
$e^{-i\gamma H_{C}}$ and $e^{-i\beta H_{B}}$, the nest commutator of $H_{B}$
and $H_{C}$ is able to span the entire Lie algebra associated with the Hilbert
space of the n-qubit system. QAOA can approximate any element of the entire
unitary group $U(2^{n})$ if a sufficient deep quantum circuit is applied [26,
27]. Based on the existing generator $H_{B}$ and $H_{C}$, S-QAOA provides an
extra generator associated with the two-body interaction to accelerate the
process of approximating the desired unitary operation. The numerical result
shows that the generator associated with the YY interaction has the best
performance, and the quantum circuit depth is reduced significantly by
including it in S-QAOA ansatz (Fig.8). The advantage of YY interaction might
be explained by the connection of it and the CD driving terms (Eq.5). For
MaxCut problem and SK model, the first order of Eq.5 is:

$\displaystyle H_{CD}^{1}=i\alpha_{1}[H_{B},H_{C}]$ (16)
$\displaystyle=-2\alpha_{1}\sum_{(i,j)}w_{ij}(Z_{i}Y_{j}+Y_{i}Z_{j}).$

There is a little improvement when we add the above $YZ$ term to the quantum
circuit Eq.13(Fig.8). The limited improvement of $YZ$ term is possibly due to
that the effective Hamiltonian of QAOA contains the first order of CD driving
terms (Eq.11). In order to introduce more counter terms to compensate the
diabatic excitations, we consider the second order of CD driving terms(Eq.13):

$H\sim\beta H_{B}+\gamma H_{C},$ (17) $\displaystyle
H_{CD}^{2}=i\alpha_{2}[H,[H,[H_{B},H_{C}]]]$ (18)
$\displaystyle=-\alpha_{2}\\{(c_{1}\beta^{2}+c_{2}\gamma^{2})\sum_{(i,j)}w_{ij}(Y_{i}Z_{j}+Z_{i}Y_{j})$
$\displaystyle+c_{3}\beta\gamma\sum_{i}\sum_{jk\in\\{n_{i}\\}}w_{ij}w_{ik}(X_{i}Z_{j}Y_{k}+X_{i}Y_{j}Z_{k})$
$\displaystyle+c_{4}\gamma^{2}\sum_{i}\sum_{jkm\in\\{n_{i}\\}}w_{ij}w_{ik}w_{im}Y_{i}Z_{j}Z_{k}Z_{m}\\},$

There are some positive coefficients $c_{1},c_{2},c_{3},c_{4}$, and
$\\{n_{i}\\}$ represent the neighbors of vertex $i$, eg. $(i,j)\in E,\forall
j\in\\{n_{i}\\}$ The first two terms on the right side of equation Eq.18 can
be generated if a series of $YY$ interaction $H_{Y}=\sum_{ij}w_{ij}Y_{i}Y_{j}$
is added to ansatz:

$\displaystyle e^{-i\alpha H_{Y}}e^{-i\beta H_{B}}e^{-i\gamma H_{C}}\sim
e^{-iH_{eff}},$ (19) $\displaystyle H_{eff}=\alpha H_{Y}+\beta H_{B}+\gamma
H_{C}$
$\displaystyle-i\frac{\beta\gamma}{2}[H_{B},H_{C}]-i\frac{\alpha\beta}{2}[H_{Y},H_{B}]-i\frac{\alpha\gamma}{2}[H_{Y},H_{C}]$
$\displaystyle=\alpha H_{Y}+\beta H_{B}+\gamma H_{C}+H_{1}+H_{2}+H_{3}.$

$H_{1}$ has the same form as the first order of CD driving terms (Eq.8).
$H_{2}$ and $H_{3}$ will generate terms same as the first two terms on the
right side of equation Eq.18:

$\displaystyle
H_{2}=-i\frac{\alpha\beta}{2}[H_{Y},H_{B}]=\alpha\beta\sum_{ij}w_{ij}(Y_{i}Z_{j}+Z_{i}Y_{j}).$
(20)

$\displaystyle H_{3}=-i\frac{\alpha\gamma}{2}[H_{Y},H_{C}]$ (21)
$\displaystyle=\alpha\gamma\sum_{i}\sum_{jk\in\\{n_{i}\\}}w_{ij}w_{ik}(X_{i}Y_{j}Z_{k}+X_{i}Z_{j}Y_{k}).$

$H_{2}$ contains the same interaction as the first term on the right side of
equation Eq.18, and $H_{3}$ contains the same interaction as the second term.
Besides, the sign of the coefficient of $H_{2}$ and $H_{3}$ are the same, it
is the same for that of Eq.18. So it can partially compensate the excited
states by adding the $YY$ interaction to S-QAOA ansatz.

Besides, the parameter freedom of ZZ interaction is released to further reduce
the quantum circuit depth, and since the strength of $YY$ and $ZZ$
interactions should be positively related, the coefficient $\gamma_{ij}$ is
added to each YY interaction:

$\displaystyle e^{-i\alpha H_{Y}}e^{-i\beta H_{B}}e^{-i\gamma
H_{C}}\rightarrow$ (22) $\displaystyle
e^{-i\alpha\sum\limits_{(ij)}w_{ij}\gamma_{ij}Y_{i}Y_{j}}e^{-i\beta\sum\limits_{i=1}^{n}X_{i}}\
e^{-i\sum\limits_{(ij)}w_{ij}\gamma_{ij}Z_{i}Z_{j}}.$

The coefficient $\alpha$ plays the same role as in STA, and is also be
determined variationally.

To reduce the number of CNOT gates, the order of operations in the ansatz is
adjusted, and the operations of the $YY$ and $ZZ$ interactions are combined
together:

$e^{-i\beta\sum\limits_{i}X_{i}}\prod\limits_{(ij)}e^{-iw_{ij}\gamma_{ij}(\alpha
Y_{i}Y_{j}+Z_{i}Z_{j})}.$ (23)

The combined implementation of YY and ZZ interactions can be realized as shown
in Fig.5. Fig.6 shows the comparison of the performance of ansatz in Eq.22 and
Eq.23 by considering the MaxCut problem on w3R graphs. The result implies that
the performance of those two ansatzes are basically the same, so we choose the
ansatz in Eq.23 to reduce the quantum circuit depth.

Figure 5: The implementations of the two-body interactions in QAOA and S-QAOA
using CNOT gate. The definitions of the single-qubit rotation gates are :
$R_{X}(\theta)=e^{-i\frac{\theta}{2}X},R_{Y}(\theta)=e^{-i\frac{\theta}{2}Y},R_{Z}(\theta)=e^{-i\frac{\theta}{2}Z}$.
As shown above, the number of CNOT gate will be the same for QAOA and S-QAOA
if introducing YY or XX interaction to S-QAOA. Other two-body interaction
types can be implemented using three CNOT gates as shown at Ref. [28]. Figure
6: The average fractional error of MaxCut problem on 10 random w3R graphs for
the comparison of Eq.22 and Eq.23. Label ‘YY not gather’ represents the ansatz
in Eq.22. Label ‘YY’ represents the ansatz in Eq.23, e.g., combining the YY
and ZZ interactions together.

##  V Summary and outlook

In this work, S-QAOA ansatz is proposed to reduce the required quantum circuit
depth. The main innovation of S-QAOA is: firstly, the extra two-body
interaction is considered in the S-QAOA to compensate the diabatic effect and
accelerate the process of quantum optimization; secondly, the parameter
freedoms of two-body interactions are released to enhance the capacity of the
quantum circuit. We study the performance of S-QAOA and QAOA on MaxCut problem
and SK model, and the simulation result implies that S-QAOA has better
performance at lower quantum layers compared with QAOA. So S-QAOA is a good
candidate to solve the combinatorial problems using NISQ.

Releasing the parameter freedom needs extra cost of optimization, the
numerical simulation shows it is cost-effective because of the greater
improvement on fidelity. In S-QAOA, further optimization is performed on the
parameters that have large gradients, and there needs more work to explore how
to release the parameter freedoms properly, e.g., how to pick out the most
critical parameters to do a further optimization. The most influential
parameters should be different for different problems, and it is important to
develop an efficient way to pick them out. Besides, in our primary
exploration, introducing more parameters in S-QAOA makes the optimization more
challenging when considering the shot noise, so the optimization methods that
are more robust to noise should be considered in further work, like COBYLA,
SPSA, etc. Furthermore, it deserves further exploration to explain the reason
for the YY interaction’s effectiveness more clearly. We will study more cases
and do simulations with noise to test and improve our idea in the next step.

###### Acknowledgements.

We thank Lingxiao Xu, Cheng Xue, Huanyu Liu and Qingsong Li for valuable
discussions and suggestions. The results of this work are simulated using
pyQpanda, and the pyQpanda package can be downloaded at
https://github.com/OriginQ/QPanda-2.

## References

  * Preskill [2018] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph] .
  * Zhou  _et al._ [2020] 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, Physical Review X 10, 10.1103/physrevx.10.021067 (2020).
  * Wurtz and Love [2021] J. Wurtz and P. J. Love, Counterdiabaticity and the quantum approximate optimization algorithm (2021), arXiv:2106.15645 [quant-ph] .
  * Xue  _et al._ [2021] C. Xue, Z.-Y. Chen, Y.-C. Wu, and G.-P. Guo, Effects of quantum noise on quantum approximate optimization algorithm, Chinese Physics Letters 38, 030302 (2021).
  * Harrigan  _et al._ [2021] M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, and et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nature Physics 17, 332–336 (2021).
  * Albash and Lidar [2018] T. Albash and D. A. Lidar, Adiabatic quantum computation, Reviews of Modern Physics 90, 10.1103/revmodphys.90.015002 (2018).
  * Poulin  _et al._ [2011] D. Poulin, A. Qarry, R. Somma, and F. Verstraete, Quantum simulation of time-dependent hamiltonians and the convenient illusion of hilbert space, Phys. Rev. Lett. 106, 170501 (2011).
  * Suzuki [1976] M. Suzuki, Generalized Trotter’s Formula and Systematic Approximants of Exponential Operators and Inner Derivations with Applications to Many Body Problems, Commun. Math. Phys. 51, 183 (1976).
  * Torrontegui  _et al._ [2013] E. Torrontegui, S. Ibáñez, S. Martínez-Garaot, M. Modugno, A. del Campo, D. Guéry-Odelin, A. Ruschhaupt, X. Chen, and J. G. Muga, Shortcuts to adiabaticity, Advances in Atomic, Molecular, and Optical Physics , 117–169 (2013).
  * Guéry-Odelin  _et al._ [2019] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. Muga, Shortcuts to adiabaticity: Concepts, methods, and applications, Reviews of Modern Physics 91, 10.1103/revmodphys.91.045001 (2019).
  * Demirplak and Rice [2003] M. Demirplak and S. A. Rice, Adiabatic population transfer with control fields, The Journal of Physical Chemistry A 107, 9937 (2003), https://doi.org/10.1021/jp030708a .
  * Demirplak and Rice [2005] M. Demirplak and S. A. Rice, Assisted adiabatic passage revisited, The Journal of Physical Chemistry B 109, 6838 (2005), pMID: 16851769, https://doi.org/10.1021/jp040647w .
  * Berry [2009] M. V. Berry, Transitionless quantum driving, Journal of Physics A: Mathematical and Theoretical 42, 365303 (2009).
  * Hegade  _et al._ [2021] N. N. Hegade, K. Paul, Y. Ding, M. Sanz, F. Albarrán-Arriagada, E. Solano, and X. Chen, Shortcuts to adiabaticity in digitized adiabatic quantum computing, Physical Review Applied 15, 10.1103/physrevapplied.15.024038 (2021).
  * Santos and Sarandy [2015] A. C. Santos and M. S. Sarandy, Superadiabatic controlled evolutions and universal quantum computation, Scientific Reports 5, 10.1038/srep15775 (2015).
  * Coulamy  _et al._ [2016] I. B. Coulamy, A. C. Santos, I. Hen, and M. S. Sarandy, Energetic cost of superadiabatic quantum computation, Frontiers in ICT 3, 10.3389/fict.2016.00019 (2016).
  * Santos and Sarandy [2017] A. C. Santos and M. S. Sarandy, Generalized shortcuts to adiabaticity and enhanced robustness against decoherence, Journal of Physics A: Mathematical and Theoretical 51, 025301 (2017).
  * Chandarana  _et al._ [2021] P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, and X. Chen, Digitized-counterdiabatic quantum approximate optimization algorithm (2021), arXiv:2107.02789 [quant-ph] .
  * Zhu  _et al._ [2020] L. Zhu, H. L. Tang, G. S. Barron, F. A. Calderon-Vargas, N. J. Mayhall, E. Barnes, and S. E. Economou, An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer (2020), arXiv:2005.10258 [quant-ph] .
  * Farhi  _et al._ [2017] E. Farhi, J. Goldstone, S. Gutmann, and H. Neven, Quantum algorithms for fixed qubit architectures (2017), arXiv:1703.06199 [quant-ph] .
  * Kolodrubetz  _et al._ [2017] M. Kolodrubetz, D. Sels, P. Mehta, and A. Polkovnikov, Geometry and non-adiabatic response in quantum and classical systems, Physics Reports 697, 1–87 (2017).
  * Pandey  _et al._ [2020] M. Pandey, P. W. Claeys, D. K. Campbell, A. Polkovnikov, and D. Sels, Adiabatic eigenstate deformations as a sensitive probe for quantum chaos, Phys. Rev. X 10, 041017 (2020).
  * Sels and Polkovnikov [2017] D. Sels and A. Polkovnikov, Minimizing irreversible losses in quantum systems by local counterdiabatic driving, Proceedings of the National Academy of Sciences 114, E3909–E3916 (2017).
  * Claeys  _et al._ [2019] P. W. Claeys, M. Pandey, D. Sels, and A. Polkovnikov, Floquet-engineering counterdiabatic protocols in quantum many-body systems, Physical Review Letters 123, 10.1103/physrevlett.123.090602 (2019).
  * Jurdjevic and Sussmann [1972] V. Jurdjevic and H. J. Sussmann, Control systems on lie groups, Journal of Differential Equations 12, 313 (1972).
  * Morales  _et al._ [2020] M. E. S. Morales, J. D. Biamonte, and Z. Zimborás, On the universality of the quantum approximate optimization algorithm, Quantum Information Processing 19, 10.1007/s11128-020-02748-9 (2020).
  * Shende  _et al._ [2004] V. V. Shende, I. L. Markov, and S. S. Bullock, Minimal universal two-qubit controlled-not-based circuits, Physical Review A 69, 10.1103/physreva.69.062321 (2004).

##  Appendix A Results With Error Bars

The results in Fig.1,2,3 are averaged over the random graphs. Typically, the
fractional error $r$ got by QAOA should be concentrated for the same class of
problems. So it is better to show the results with error bars to represent the
variance in the fractional error, and determine whether the performance
difference between S-QAOA and QAOA is outside the margin of errors. Fig.7
shows the fractional errors with error bars for Maxcut problems and SK model.
Though there is a relatively large error bar because of the limited
statistics, the performance of S-QAOA (labeled by ‘YY’) is better than QAOA
significantly.

Figure 7: Fractional errors with error bars. The results of each problem
averaged over 20 random graphs, and the error bars are the standard deviation
of the fractional error r for those random graphs.

##  Appendix B Additional Figures

Except for the existing ZZ interaction in QAOA ansatz, S-QAOA contains other
two-body interactions to accelerate the process of quantum optimization.
Operation of each layer $k\in[1,p]$ of S-QAOA is:

$\prod\limits_{k=1}^{p}\\{e^{i\beta_{k}\sum\limits_{i}^{n}X_{i}}\prod\limits_{ij}\\{e^{-i\gamma^{ij}_{k}w_{ij}Z_{i}Z_{j}}e^{-i\alpha_{k}\gamma^{ij}_{k}w_{ij}M_{ij}}\\}\\},$
(24)

$M_{ij}$ is a two-gate term and there are five possible types of it:
$M_{ij}=\frac{P_{i}Q_{j}+Q_{i}P_{j}}{2},PQ\in\\{YZ,YY,XX,XZ,XY\\}$. To choose
the best one in these two-gate terms, we do a comprehensive simulation for
MaxCut problem and SK model, and the result can be found in Fig.8. The
simulation result implies that the $M_{ij}=Y_{i}Y_{j}$ has the best
performance in all cases. A further study in Fig.9 is to explore the necessity
of adding more two-body interactions in the ansatz, and it is obvious that the
ansatz adding more interactions can not get better performance than the ansatz
just adding YY interaction. So it is enough to just add the YY interaction in
S-QAOA ansatz.

Figure 8: Comparison of the performance of all the possible additional two-
body interactions: $\\{YZ,YY,XX,XZ,XY\\}$, the results are averaged on 10
random graphs for every case. YY interaction performs best for all the three
cases we study. The performance of XZ, XY, and ZZ types are almost the same,
so it demonstrates that the XZ and XY interactions have little effect on the
QAOA. Figure 9: Comparison of the performance of only adding the YY
interaction to the ansatz and adding two or three additional interactions to
the ansatz, which are combination of: $\\{YZ,YY,XX\\}$ interactions, e.g.,
‘YZ_YY’, ‘YZ_XX’, ‘YY_XX’ represent there are two additional interactions
followed by each ZZ interaction; ‘YZ_YY_XX’ represents the YZ, YY, XX
interactions followed by ZZ interaction one by one. The results are averaged
on 10 random graphs, and the performance of the ansatz that includes two or
three additional interactions is almost the same as the ansatz that only
includes the YY interaction. So if we consider two-gate terms, it is enough to
add the YY interaction to accelerate the evolution.