# Proximity effect in PbTe-Pb hybrid nanowire Josephson junctions

Zitong Zhang  equal contribution State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing 100084,
China  Wenyu Song  equal contribution State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing 100084,
China  Yichun Gao  equal contribution State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing 100084,
China  Yuhao Wang  equal contribution State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing 100084,
China  Zehao Yu  State Key Laboratory of Low Dimensional Quantum Physics,
Department of Physics, Tsinghua University, Beijing 100084, China  Shuai Yang
Beijing Academy of Quantum Information Sciences, Beijing 100193, China  Yuying
Jiang  State Key Laboratory of Low Dimensional Quantum Physics, Department of
Physics, Tsinghua University, Beijing 100084, China  Wentao Miao  State Key
Laboratory of Low Dimensional Quantum Physics, Department of Physics, Tsinghua
University, Beijing 100084, China  Ruidong Li  State Key Laboratory of Low
Dimensional Quantum Physics, Department of Physics, Tsinghua University,
Beijing 100084, China  Fangting Chen  State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing 100084,
China  Zuhan Geng  State Key Laboratory of Low Dimensional Quantum Physics,
Department of Physics, Tsinghua University, Beijing 100084, China  Qinghua
Zhang  Institute of Physics, Chinese Academy of Sciences, Beijing 100190,
China  Fanqi Meng  School of Materials Science and Engineering, Tsinghua
University, Beijing 100084, China  Ting Lin  Institute of Physics, Chinese
Academy of Sciences, Beijing 100190, China  Lin Gu  School of Materials
Science and Engineering, Tsinghua University, Beijing 100084, China  Kejing
Zhu  Beijing Academy of Quantum Information Sciences, Beijing 100193, China
Yunyi Zang  Beijing Academy of Quantum Information Sciences, Beijing 100193,
China  Lin Li  Beijing Academy of Quantum Information Sciences, Beijing
100193, China  Runan Shang  Beijing Academy of Quantum Information Sciences,
Beijing 100193, China  Xiao Feng  State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing 100084,
China  Beijing Academy of Quantum Information Sciences, Beijing 100193, China
Frontier Science Center for Quantum Information, Beijing 100084, China  Qi-Kun
Xue  State Key Laboratory of Low Dimensional Quantum Physics, Department of
Physics, Tsinghua University, Beijing 100084, China  Beijing Academy of
Quantum Information Sciences, Beijing 100193, China  Frontier Science Center
for Quantum Information, Beijing 100084, China  Southern University of Science
and Technology, Shenzhen 518055, China  Ke He<EMAIL_ADDRESS>State Key
Laboratory of Low Dimensional Quantum Physics, Department of Physics, Tsinghua
University, Beijing 100084, China  Beijing Academy of Quantum Information
Sciences, Beijing 100193, China  Frontier Science Center for Quantum
Information, Beijing 100084, China  Hao Zhang<EMAIL_ADDRESS>State Key Laboratory of Low Dimensional Quantum Physics, Department of
Physics, Tsinghua University, Beijing 100084, China  Beijing Academy of
Quantum Information Sciences, Beijing 100193, China  Frontier Science Center
for Quantum Information, Beijing 100084, China

###### Abstract

Semiconductor-superconductor hybrid nanowires are a leading material platform
for the realization of Majorana zero modes. The semiconductors in previous
studies are dominantly InAs or InSb. In this work, we show the induced
superconductivity in a PbTe nanowire epitaxially coupled to a superconductor
Pb. The Josephson junction device based on this hybrid reveals a gate-tunable
supercurrent in the open regime and a hard superconducting gap in the
tunneling regime. By demonstrating the superconducting proximity effect, our
result can enable Majorana searches and other applications like gate-tunable
qubits in a new semiconductor system.

A semiconductor nanowire coupled to a superconductor is an intriguing quantum
system owing to the proximity effect. One such example is the gate-tunable
Josephson junction [1] which plays a key role in the gatemon superconducting
qubit [2]. Moreover, the interplay between the strong spin-orbit coupling in
the semiconductor and the Zeeman energy may lead to topological phases hosting
Majorana zero modes [3, 4, 5, 6]. InAs and InSb nanowires are the
semiconductors commonly used in those studies due to several practical
reasons, e.g., the well established state-of-art device fabrication and
control [7, 8, 9], epitaxial growth of superconductors [10, 11, 12] and the
strong spin-orbit interaction [13, 14]. These advantages are all crucial and
indeed have enabled tremendous experimental progress on possible Majorana
signatures [15, 16, 17, 18, 19, 20, 21]. The current roadblock is device
disorder which has to be improved first before further progress [22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33].

To overcome this challenge, PbTe nanowires have recently been proposed as a
potentially better candidate [34]. The hope is that the large dielectric
constant ($\sim$ 1350) in PbTe can significantly screen charge disorder.
Moreover, growing PbTe on a lattice-matched substrate, CdTe, can further
reduce the substrate disorder [35]. Finally, capping the PbTe with CdTe can
push the surface disorder away from the core region of the device. Quickly,
experimental efforts [35, 36, 37, 38, 39] have been carried out on the growth
of PbTe nanowires with transport characterizations on the field effect
mobility, weak anti-localization, Aharonov-Bohm oscillations and quantum dots.
So far, the key question of whether superconducting proximity effect in PbTe
nanowires exists is still pending. Here, we demonstrate the induced
superconductivity in a PbTe nanowire coupled to a superconductor Pb. Two
hallmark transport signatures can be revealed in a Josephson junction (JJ)
device based on this hybrid: a gate-tunable supercurrent in the open regime
and a hard superconducting gap in the tunneling regime. Our result may open
the door to a new wave of Majorana studies and also other quantum devices,
e.g. hybrid qubits [2].

Figure 1:  (a) SEM of a PbTe-Pb nanowire. Scale bar, 1 $\mu$m. (b) The JJ
schematic, cut at the red dashed line in (a). Layer thickness on the right.
(c) SEM of device A. Scale bar, 1 $\mu$m. Contacts and gate, Ti/Au (10/65 nm).
(d) Device schematic.

Figure 1 shows the scanning electron micrograph (SEM) of a PbTe-Pb nanowire
and its device schematic. The nanowire growth is similar to that in Ref. [35]
with minor modifications. The CdTe substrate was first covered by SixNy.
Nanowire-shape trenches were defined by etching SixNy using reactive ion
etching. The chip was then loaded into a molecular beam epitaxy chamber for
the nanowire growth. The chip was cleaned with Ar treatment, annealed at 240.6
∘C, and then followed by selective area growth of the CdTe buffer. This
procedure ensures that the PbTe nanowire is spatially separated from the
disorder generated during the substrate cleaning. PbTe was then grown,
followed by the Pb film deposition at a tilted angle without breaking vacuum.
The standing wall shadowed part of the PbTe nanowire, forming a JJ. The entire
chip was then capped by CdTe to prevent oxidation. Figure 1(a) is the SEM
after growth and Fig. 1(b) is the JJ layer structure (not in scale).

For device fabrication, most of the Pb film on the substrate was etched using
Ar ion milling to prevent a short circuit. Source/drain (S/D) electrodes and a
side gate were fabricated by evaporating Ti/Au. Ar-plasma etching was
performed before the evaporation to remove the CdTe capping in the contact
regions for ohmic contacts. Figures 1(c) and 1(d) show the SEM and a 3D
schematic of the final device. For the growth and fabrication details, see the
method section in the supplementary materials (SM). The device was measured in
a dilution fridge at a base temperature $T\sim$15 mK using the standard two-
terminal set-up.

Figure 2: Supercurrent in the open regime of Device A. (a) $I$-$V$
characteristic as a function of $V_{\text{G}}$. $B$ = 0 T. (b) Line cuts from
(a). (c) $I_{\text{excess}}$ and $R_{\text{n}}$ estimations of an example
$I$-$V$ trace. (d) Estimated PbTe-Pb interface transparency. Red and blue dots
are based on the $I_{\text{excess}}$ and $R_{\text{n}}$ extracted from the
positive and negative bias branches, respectively. (e) $R$ versus $I$ and $B$.
$R=$d$V/$d$I$. $B$ is parallel to the nanowire. (f) Line cuts from (e). (g)
$R$ versus $I$ and $B$. $B$ is perpendicular to the substrate. (h) Line cuts
from (g). (i) $T$ dependence.

Figure 2(a) shows the $I$-$V$ characteristic of the JJ as a function of gate
voltage ($V_{\text{G}}$). The “white triangle” is the gate-tunable
supercurrent region, see Fig. 2(b) for line cuts. A series resistance
($R_{\text{series}}$), including the filters ($\sim$3.5 k$\Omega$) and
contacting resistance ($\sim$400 $\Omega$), is subtracted from the raw two-
terminal $I$-$V$ curve. See Fig. S1 in SM for details. The current sweeps from
negative to positive. The current bias at which the JJ jumps from the
superconducting to the resistive branch defines the switching current
$I_{\text{s}}$. $I_{\text{s}}$ of 78 nA translates to a Josephson energy
$E_{\text{J}}=\hbar I_{\text{c}}/2e\sim$160 $\mu$eV, well exceeding the
typical $E_{\text{J}}$ (90 $\mu$eV) for a gatemon [2]. We expect the critical
current $I_{\text{c}}$ to be close to $I_{\text{s}}$ since the fridge $T$ is
much less than $E_{\text{J}}$ ($\sim$1.8 K). The “switching point” from the
resistive to the superconducting branch (the negative current bias) defines
the retrapping current $I_{\text{r}}$. $I_{\text{r}}$ being almost identical
to $I_{\text{s}}$ suggests that the JJ is in the over-damped regime.

To study the PbTe-Pb interface transparency, Fig. 2(c) shows an $I$-$V$ curve
over a larger $I$ range. The linear fit (red dashed line) for $V>2\Delta$
extracts the JJ normal state resistance, $R_{\text{n}}\sim$941 $\Omega$.
$\Delta$ is the size of the superconducting gap (see Fig. 3). Extending the
red dashed line to the $I$ axis gives the excess current,
$I_{\text{excess}}\sim$307 nA. We then calculate
$eI_{\text{excess}}R_{\text{n}}/\Delta\sim$0.69, which can be further used to
estimate the junction transparency ($\sim$0.65) [40, 41]. Figure 2(d) shows
the transparency as a function of $V_{\text{G}}$. The transparency (equals to
$1/(1+Z^{2})$) is calculated by solving the equation of $Z$:
$eI_{\text{excess}}R_{\text{n}}/\Delta=2(1+2Z^{2})\times\text{tanh}^{-1}[2Z\sqrt{(1+Z^{2})/(1+6Z^{2}+4Z^{4})}]\times[Z\sqrt{(1+Z^{2})(1+6Z^{2}+4Z^{4})}]^{-1}-4/3$
[42]. The red (blue) dots used $I_{\text{excess}}$ and $R_{\text{n}}$
extracted from the positive (negative) bias axis in Fig. 2(c). The maximum
transparency exceeding 0.8 indicates a high quality PbTe-Pb interface. Note
that the extracted transparency here is probably underestimated since $\Delta$
of 0.42 meV (in the tunneling regime) is used. $\Delta$ in the open regime is
smaller (see Fig. 3). For detailed analysis of $I_{\text{excess}}$,
$I_{\text{s}}$ and $R_{\text{n}}$, see Fig. S2 in SM.

Figures 2(e) and 2(f) show the magnetic field ($B$) dependence of the
supercurrent. $B$ is roughly parallel to the nanowire axis. For clarity, the
differential resistance, $R=$d$V/$d$I$, is presented. $I_{\text{s}}$ decreases
monotonically, suggesting that the orbital effect in PbTe does not play a
significant role. In Fig. S3 in SM, we show another device which resolves
clear supercurrent interference possibly due to the orbital effect in the PbTe
nanowire. In Figs. 2(g) and 2(h), $B$ is aligned perpendicular to the
substrate (Pb film) and the supercurrent is suppressed at $\sim$0.07 T. This
field value is roughly consistent with the critical field (0.08 T) of a bulk
superconductor Pb. For $B$ parallel to the nanowire (Fig. 2(e)), the critical
field is two times larger, indicating less orbital effect in the Pb film (the
effective Pb area perpendicular to $B$ is smaller due to the thin thickness of
the film). The multiple peaks are subgap features ($V<2\Delta/e$) likely
result from multiple Andreev reflections (MARs) [43]. For completeness, we
show the $T$ dependence of the supercurrent in Fig. 2(i). The supercurrent is
fully suppressed at $T\sim$1 K, much smaller than the critical $T$ of a bulk
Pb ($\sim$7 K).

Driving $V_{\text{G}}$ more negative lowers the junction transmission and
reaches the tunneling regime. The differential conductance,
$\text{d}I/\text{d}V$, in this regime can resolve the superconducting gap as
shown in Fig. 3(a). The two peaks, symmetrically located at $V\sim\pm$0.84 mV,
correspond to the 2$\Delta$ coherence peaks, see Fig. 3(b) for the line cut.
The negative differential conductance outside the gap (next to the coherence
peak) is typical for S-NW-S devices (S for superconductor and NW for nanowire)
[8]. The subgap conductance reaches zero (close to the measurement noise
level), suggesting a hard superconducting gap. The ratio of outside gap versus
subgap conductance is close to two orders of magnitude. Note that for S-NW-S
devices, the tunneling conductance reflects the convolution of two density of
states (DOS) of superconductor quasiparticles. To directly reveal the DOS, an
N-NW-S device (N for normal metal) is more appropriate. More positive
$V_{\text{G}}$ in Fig. 3(a) reveals a sharp zero-bias conductance peak,
resulting from the supercurrent (in the open regime). Several subgap peaks are
also visible in Fig. 3(a), possibly due to MARs [43] (see Fig. S2 in SM for
additional analysis).

Figure 3: Superconducting gap in the tunneling regime of Device A. (a)
$\text{d}I/\text{d}V$ versus $V$ for more negative $V_{\text{G}}$. $B$ = 0 T.
(b) A line cut in the tunneling regime, plotted in linear (upper) and
logarithmic (lower) scales. (c) $B$ (parallel to the nanowire) dependence of
the gap. (d) Line cuts from (c). (e) $B$ is perpendicular to the substrate.
(f) Line cuts from (e). (g) $T$ dependence of the gap.

The size of the induced gap $\Delta\sim$0.42 meV is significantly smaller than
the gap of a bulk Pb, estimated based on the formula
$\Delta=1.76k_{\text{B}}T_{\text{c}}\sim$1.1 meV ($T_{\text{c}}\sim$7 K for
Pb). In a recent work on InAs epitaxially coupled to Pb [44], an induced gap
of 1.1-1.5 meV is reported with the Pb film thickness being 9-50 nm. As a
comparison, our Pb film thickness is $\sim$23 nm. The relatively small induced
gap suggests that our PbTe-Pb is likely not in the strong coupling regime, but
rather an intermediate coupling case. The advantages and disadvantages for
strong and intermediate couplings have been extensively studied in theory [45,
46, 47, 48]. Most of the current hybrid nanowires (InAs-Al, InAs-Pb and InSb-
Al) are in the strong coupling regime. Our device provides a platform to study
the proximity effect in the intermediate coupling regime, shedding light on
e.g., the role of disorder in the superconductor [49, 50].

Another notable feature in Fig. 3(a) is the variation of the gap size: The gap
“shrinks” for a more positive $V_{\text{G}}$. We have independently calibrated
the fridge filters and confirm that this shrink is not due to an
overestimation of $R_{\text{series}}$ and its shared bias voltage. A possible
explanation for the shrink is the gate-tunable superconductor-semiconductor
coupling [51]. More positive $V_{\text{G}}$ “drags” the electron wavefunctions
more into the PbTe (less in Pb), leading to a smaller induced gap. Though the
side gate has a “finger” shape, the large dielectric constant of PbTe can bend
the electric field lines such that $V_{\text{G}}$ can also tune the
proximitized PbTe parts [38].

Figures 3(c)-(f) show the $B$ dependence of the gap, resolving a critical
field of $\sim$0.9 T for parallel $B$ and $\sim$0.3 T for perpendicular $B$.
The critical field of a bulk Pb is 0.08 T. The differences between these three
values indicate the reduced orbital effect in Pb for smaller sizes. To achieve
higher critical field (a few Tesla), a thinner ($\sim$10 nm) Pb film is needed
in future devices [44].

The small oscillations outside the gap in Figs. 3(d) and 3(f) (also visible in
Fig. 3(a)) are reminiscent of those in Ref. [52]. Since the PbTe-Pb interface
is rather flat, we think the oscillations are likely caused by the nonuniform
PbTe-CdTe interface. Though the substrate is typically flat after the growth
of the CdTe buffer, PbTe growth requires heating the substrate to 318.5 ∘C to
have selectivity. This temperature can evaporate part of the CdTe buffer,
causing the non-flat interface (see Fig. S4 in SM). Electron back scattering
can occur, leading to those Fabry-Perot-like oscillations. This non-uniformity
surely degrades the device quality and should be minimized in future
optimizations. In Fig. S3, we show two devices which can not be pinched off
before the gate leaks, possibly due to this substrate disorder.

Figure 4: STEM analysis of device B. (a) HAADF image of the nanowire cross-
section with crystal directions labeled. (b) Atomically resolved image near
the Pb-CdTe (capping) interface, see the blue box in (a). (c) Image of the
PbTe-CdTe interface, see the green box in (a). (d) Image of the PbTe-Pb
interface, see the violet box in (a). (e)-(f), EDX maps of Pb, Te, Cd and Si,
respectively. Scale bar, 50 nm.

Figure 3(g) shows the $T$ dependence of the gap. The gap is completely “washed
out” at $\sim$4 K. The small oscillations, however, are still present. This is
consistent with our interpretation above: The normal scattering (Fabry-Perot-
like) can have a different energy scale than the superconducting correlations.
In Figs. 3(d) and 3(f), the oscillations can be suppressed, possibly due to
the accumulated phases induced by $B$.

After the quantum transport characterization, we cut the device cross-section
using a focused ion beam and performed the high-resolution scanning
transmission electron microscopy (STEM). Figure 4(a) shows the image of the
cross-section lamella from another device (device B). The lamella of device A
was damaged by the focused ion milling (see Fig. S4 in SM). Devices A and B
were grown and fabricated together (on one same substrate chip). The transport
study of device B is shown in Fig. S3 in SM. The high-angle annular dark field
(HAADF) image in Fig. 4(a) clearly shows different material layers with sharp
interfaces. The green arrow points to a dark line region in the CdTe(001),
likely the residue of Ar treatment during the substrate cleaning. By growing
the CdTe buffer before PbTe, we can “bury” this disordered region in the CdTe,
away from the PbTe nanowire. We find that this buffer growth can significantly
improve the device transport quality compared to our previous study [35]. The
violet arrow indicates a corner of the Pb film which was damaged during the
lamella preparation. For additional STEM analysis on device B, see Fig. S5 in
SM.

Figures 4(b)-(d) show the atomically resolved STEM images at three key
interfaces: the Pb-CdTe (capping), the PbTe-CdTe (substrate buffering) and the
PbTe-Pb. The PbTe and CdTe are lattice matched (Fig. 4(c)). The PbTe-Pb
interface is also sharp but with mismatched dislocations. This disorder could
be reduced in the future by growing a thin layer of CdTe between the PbTe and
the Pb growth. The CdTe capping in Fig. 4(b) prevents the oxidation of the Pb
film underneath. The lattice mismatch between Pb and CdTe is a disorder source
in the superconductor. This disorder may enhance the proximity effect [45] and
its disadvantage needs further systematic studies. The energy-dispersive x-ray
spectroscopy (EDX) maps of the four elements Pb, Te, Cd and Si (for the
dielectric mask) are shown in Figs. 4(e)-(h). Both the STEM and the EDX
suggest little interlayer diffusion.

To summarize, we have studied the superconducting proximity effect in PbTe-Pb
hybrid nanowires. A Josephson junction device based on this hybrid reveals a
gate-tunable supercurrent in the open regime and a hard induced
superconducting gap in the tunneling regime. Though the device is far from
perfect and more optimizations are still needed (e.g. substrate uniformity),
our work shows that the combination of PbTe and Pb could work as a new hybrid
nanowire system for Majorana searches.

Acknowledgment This work is supported by Tsinghua University Initiative
Scientific Research Program, National Natural Science Foundation of China
(92065206) and the Innovation Program for Quantum Science and Technology
(2021ZD0302400). Raw data and processing codes within this paper are available
at https://doi.org/10.5281/zenodo.7398019.

## References

  * Doh  _et al._ [2005] Y.-J. Doh, J. A. van Dam, A. L. Roest, E. P. A. M. Bakkers, L. P. Kouwenhoven, and S. D. Franceschi, Tunable supercurrent through semiconductor nanowires, Science 309, 272 (2005).
  * Larsen  _et al._ [2015] T. W. Larsen, K. D. Petersson, F. Kuemmeth, T. S. Jespersen, P. Krogstrup, J. Nygård, and C. M. Marcus, Semiconductor-nanowire-based superconducting qubit, Phys. Rev. Lett. 115, 127001 (2015).
  * Lutchyn  _et al._ [2010] R. M. Lutchyn, J. D. Sau, and S. Das Sarma, Majorana fermions and a topological phase transition in semiconductor-superconductor heterostructures, Phys. Rev. Lett. 105, 077001 (2010).
  * Oreg  _et al._ [2010] Y. Oreg, G. Refael, and F. von Oppen, Helical liquids and majorana bound states in quantum wires, Phys. Rev. Lett. 105, 177002 (2010).
  * Prada  _et al._ [2020] E. Prada, P. San-Jose, M. W. de Moor, A. Geresdi, E. J. Lee, J. Klinovaja, D. Loss, J. Nygård, R. Aguado, and L. P. Kouwenhoven, From andreev to majorana bound states in hybrid superconductor–semiconductor nanowires, Nature Reviews Physics 2, 575 (2020).
  * Zhang  _et al._ [2019] H. Zhang, D. E. Liu, M. Wimmer, and L. P. Kouwenhoven, Next steps of quantum transport in majorana nanowire devices, Nature Communications 10, 5128 (2019).
  * Kammhuber  _et al._ [2016] J. Kammhuber, M. C. Cassidy, H. Zhang, Ö. Gül, F. Pei, M. W. de Moor, B. Nijholt, K. Watanabe, T. Taniguchi, D. Car, _et al._ , Conductance quantization at zero magnetic field in insb nanowires, Nano letters 16, 3482 (2016).
  * Gül  _et al._ [2017] Ö. Gül, H. Zhang, F. K. de Vries, J. van Veen, K. Zuo, V. Mourik, S. Conesa-Boj, M. P. Nowak, D. J. van Woerkom, M. Quintero-Pérez, _et al._ , Hard superconducting gap in insb nanowires, Nano letters 17, 2690 (2017).
  * Zhang  _et al._ [2017] H. Zhang, Ö. Gül, S. Conesa-Boj, M. P. Nowak, M. Wimmer, K. Zuo, V. Mourik, F. K. De Vries, J. Van Veen, M. W. De Moor, _et al._ , Ballistic superconductivity in semiconductor nanowires, Nature Communications 8, 16025 (2017).
  * Chang  _et al._ [2015] W. Chang, S. Albrecht, T. Jespersen, F. Kuemmeth, P. Krogstrup, J. Nygård, and C. M. Marcus, Hard gap in epitaxial semiconductor–superconductor nanowires, Nature nanotechnology 10, 232 (2015).
  * Op Het Veld  _et al._ [2020] R. Op Het Veld, D. Xu, V. Schaller, M. Verheijen, S. Peters, J. Jung, C. Tong, Q. Wang, M. Moor, B. Hesselmann, K. Vermeulen, J. Bommer, J. S. Lee, A. Sarikov, M. Pendharkar, A. Marzegalli, S. Koelling, L. Kouwenhoven, L. Miglio, and E. Bakkers, In-plane selective area insb–al nanowire quantum networks, Communications Physics 3 (2020).
  * Pan  _et al._ [2022a] D. Pan, H. Song, S. Zhang, L. Liu, L. Wen, D. Liao, R. Zhuo, Z. Wang, Z. Zhang, S. Yang, J. Ying, W. Miao, R. Shang, H. Zhang, and J. Zhao, In situ epitaxy of pure phase ultra-thin inas-al nanowires for quantum devices, Chinese Physics Letters 39, 058101 (2022a).
  * van Weperen  _et al._ [2015] I. van Weperen, B. Tarasinski, D. Eeltink, V. S. Pribiag, S. R. Plissard, E. P. A. M. Bakkers, L. P. Kouwenhoven, and M. Wimmer, Spin-orbit interaction in insb nanowires, Phys. Rev. B 91, 201413 (2015).
  * Bommer  _et al._ [2019] J. D. Bommer, H. Zhang, Ö. Gül, B. Nijholt, M. Wimmer, F. N. Rybakov, J. Garaud, D. Rodic, E. Babaev, M. Troyer, _et al._ , Spin-orbit protection of induced superconductivity in majorana nanowires, Physical Review Letters 122, 187702 (2019).
  * Mourik  _et al._ [2012] V. Mourik, K. Zuo, S. M. Frolov, S. Plissard, E. P. Bakkers, and L. P. Kouwenhoven, Signatures of majorana fermions in hybrid superconductor-semiconductor nanowire devices, Science 336, 1003 (2012).
  * Deng  _et al._ [2016] M. Deng, S. Vaitiekėnas, E. B. Hansen, J. Danon, M. Leijnse, K. Flensberg, J. Nygård, P. Krogstrup, and C. M. Marcus, Majorana bound state in a coupled quantum-dot hybrid-nanowire system, Science 354, 1557 (2016).
  * Albrecht  _et al._ [2016] S. Albrecht, A. Higginbotham, M. Madsen, F. Kuemmeth, T. Jespersen, J. Nygård, P. Krogstrup, and C. Marcus, Exponential protection of zero modes in majorana islands, Nature 531, 206 (2016).
  * Gül  _et al._ [2018] Ö. Gül, H. Zhang, J. D. Bommer, M. W. de Moor, D. Car, S. R. Plissard, E. P. Bakkers, A. Geresdi, K. Watanabe, T. Taniguchi, _et al._ , Ballistic majorana nanowire devices, Nature Nanotechnology 13, 192 (2018).
  * Zhang  _et al._ [2021] H. Zhang _et al._ , Large zero-bias peaks in insb-al hybrid semiconductor-superconductor nanowire devices, arXiv: 2101.11456 (2021).
  * Song  _et al._ [2022] H. Song, Z. Zhang, D. Pan, D. Liu, Z. Wang, Z. Cao, L. Liu, L. Wen, D. Liao, R. Zhuo, D. E. Liu, R. Shang, J. Zhao, and H. Zhang, Large zero bias peaks and dips in a four-terminal thin inas-al nanowire device, Phys. Rev. Research 4, 033235 (2022).
  * Wang  _et al._ [2022] Z. Wang, H. Song, D. Pan, Z. Zhang, W. Miao, R. Li, Z. Cao, G. Zhang, L. Liu, L. Wen, R. Zhuo, D. E. Liu, K. He, R. Shang, J. Zhao, and H. Zhang, Plateau regions for zero-bias peaks within 5$\%$ of the quantized conductance value $2{e}^{2}/h$, Phys. Rev. Lett. 129, 167702 (2022).
  * Prada  _et al._ [2012] E. Prada, P. San-Jose, and R. Aguado, Transport spectroscopy of ns nanowire junctions with majorana fermions, Physical Review B 86, 180503 (2012).
  * Liu  _et al._ [2012] J. Liu, A. C. Potter, K. T. Law, and P. A. Lee, Zero-bias peaks in the tunneling conductance of spin-orbit-coupled superconducting wires with and without majorana end-states, Phys. Rev. Lett. 109, 267002 (2012).
  * Liu  _et al._ [2017] C.-X. Liu, J. D. Sau, T. D. Stanescu, and S. D. Sarma, Andreev bound states versus majorana bound states in quantum dot-nanowire-superconductor hybrid structures: Trivial versus topological zero-bias conductance peaks, Physical Review B 96, 075161 (2017).
  * Liu  _et al._ [2018] D. E. Liu, E. Rossi, and R. M. Lutchyn, Impurity-induced states in superconducting heterostructures, Phys. Rev. B 97, 161408 (2018).
  * Cao  _et al._ [2019] Z. Cao, H. Zhang, H.-F. Lü, W.-X. He, H.-Z. Lu, and X. C. Xie, Decays of majorana or andreev oscillations induced by steplike spin-orbit coupling, Phys. Rev. Lett. 122, 147701 (2019).
  * Reeg  _et al._ [2018] C. Reeg, O. Dmytruk, D. Chevallier, D. Loss, and J. Klinovaja, Zero-energy andreev bound states from quantum dots in proximitized rashba nanowires, Physical Review B 98, 245407 (2018).
  * Pan and Das Sarma [2020] H. Pan and S. Das Sarma, Physical mechanisms for zero-bias conductance peaks in majorana nanowires, Phys. Rev. Research 2, 013377 (2020).
  * Das Sarma and Pan [2021] S. Das Sarma and H. Pan, Disorder-induced zero-bias peaks in majorana nanowires, Phys. Rev. B 103, 195158 (2021).
  * Ahn  _et al._ [2021] S. Ahn, H. Pan, B. Woods, T. D. Stanescu, and S. Das Sarma, Estimating disorder and its adverse effects in semiconductor majorana nanowires, Phys. Rev. Materials 5, 124602 (2021).
  * Pan  _et al._ [2022b] H. Pan, J. D. Sau, and S. Das Sarma, Random matrix theory for the robustness, quantization, and end-to-end correlation of zero-bias conductance peaks in a class d ensemble, Phys. Rev. B 106, 115413 (2022b).
  * Zeng  _et al._ [2022] C. Zeng, G. Sharma, S. Tewari, and T. Stanescu, Partially separated majorana modes in a disordered medium, Phys. Rev. B 105, 205122 (2022).
  * Lai  _et al._ [2022] Y.-H. Lai, S. Das Sarma, and J. D. Sau, Quality factor for zero-bias conductance peaks in majorana nanowire, Phys. Rev. B 106, 094504 (2022).
  * Cao  _et al._ [2022] Z. Cao, D. E. Liu, W.-X. He, X. Liu, K. He, and H. Zhang, Numerical study of pbte-pb hybrid nanowires for engineering majorana zero modes, Phys. Rev. B 105, 085424 (2022).
  * Jiang  _et al._ [2022] Y. Jiang, S. Yang, L. Li, W. Song, W. Miao, B. Tong, Z. Geng, Y. Gao, R. Li, F. Chen, Q. Zhang, F. Meng, L. Gu, K. Zhu, Y. Zang, R. Shang, Z. Cao, X. Feng, Q.-K. Xue, D. E. Liu, H. Zhang, and K. He, Selective area epitaxy of pbte-pb hybrid nanowires on a lattice-matched substrate, Phys. Rev. Materials 6, 034205 (2022).
  * Schellingerhout  _et al._ [2022] S. G. Schellingerhout, E. J. de Jong, M. Gomanko, X. Guan, Y. Jiang, M. S. M. Hoskam, J. Jung, S. Koelling, O. Moutanabbir, M. A. Verheijen, S. M. Frolov, and E. P. A. M. Bakkers, Growth of pbte nanowires by molecular beam epitaxy, Materials for Quantum Technology 2, 015001 (2022).
  * Geng  _et al._ [2022] Z. Geng, Z. Zhang, F. Chen, S. Yang, Y. Jiang, Y. Gao, B. Tong, W. Song, W. Miao, R. Li, Y. Wang, Q. Zhang, F. Meng, L. Gu, K. Zhu, Y. Zang, L. Li, R. Shang, X. Feng, Q.-K. Xue, K. He, and H. Zhang, Observation of aharonov-bohm effect in pbte nanowire networks, Phys. Rev. B 105, L241112 (2022).
  * Kate  _et al._ [2022] S. Kate, M. Ritter, A. Fuhrer, J. Jung, S. Schellingerhout, E. Bakkers, H. Riel, and F. Nichele, Small charging energies and g -factor anisotropy in pbte quantum dots, Nano Letters 22 (2022).
  * [39] J. Jung, S. G. Schellingerhout, M. F. Ritter, S. C. ten Kate, O. A. van der Molen, S. de Loijer, M. A. Verheijen, H. Riel, F. Nichele, and E. P. Bakkers, Selective area growth of pbte nanowire networks on inp, Advanced Functional Materials n/a, 2208974.
  * Blonder  _et al._ [1982] G. Blonder, m. M. Tinkham, and k. T. Klapwijk, Transition from metallic to tunneling regimes in superconducting microconstrictions: Excess current, charge imbalance, and supercurrent conversion, Physical Review B 25, 4515 (1982).
  * Flensberg  _et al._ [1988] K. Flensberg, J. B. Hansen, and M. Octavio, Subharmonic energy-gap structure in superconducting weak links, Phys. Rev. B 38, 8707 (1988).
  * Niebler  _et al._ [2009] G. Niebler, G. Cuniberti, and T. Novotný, Analytical calculation of the excess current in the octavio–tinkham–blonder–klapwijk theory, Superconductor Science and Technology 22, 085016 (2009).
  * Octavio  _et al._ [1983] M. Octavio, M. Tinkham, G. E. Blonder, and T. M. Klapwijk, Subharmonic energy-gap structure in superconducting constrictions, Phys. Rev. B 27, 6739 (1983).
  * Kanne  _et al._ [2021] T. Kanne, M. Marnauza, D. Olsteins, D. Carrad, J. E. Sestoft, J. Bruijckere, L. Zeng, E. Johnson, E. Olsson, K. Grove-Rasmussen, and J. Nygård, Epitaxial pb on inas nanowires for quantum devices, Nature Nanotechnology 16, 1 (2021).
  * Antipov  _et al._ [2018] A. E. Antipov, A. Bargerbos, G. W. Winkler, B. Bauer, E. Rossi, and R. M. Lutchyn, Effects of gate-induced electric fields on semiconductor majorana nanowires, Phys. Rev. X 8, 031041 (2018).
  * Mikkelsen  _et al._ [2018] A. E. G. Mikkelsen, P. Kotetes, P. Krogstrup, and K. Flensberg, Hybridization at superconductor-semiconductor interfaces, Phys. Rev. X 8, 031040 (2018).
  * Woods  _et al._ [2018] B. D. Woods, T. D. Stanescu, and S. Das Sarma, Effective theory approach to the schrödinger-poisson problem in semiconductor majorana devices, Phys. Rev. B 98, 035428 (2018).
  * Reeg  _et al._ [2017] C. Reeg, D. Loss, and J. Klinovaja, Finite-size effects in a nanowire strongly coupled to a thin superconducting shell, Phys. Rev. B 96, 125426 (2017).
  * Cole  _et al._ [2016] W. S. Cole, J. D. Sau, and S. Das Sarma, Proximity effect and majorana bound states in clean semiconductor nanowires coupled to disordered superconductors, Phys. Rev. B 94, 140505 (2016).
  * Stanescu and Das Sarma [2022] T. D. Stanescu and S. Das Sarma, Proximity-induced superconductivity generated by thin films: Effects of fermi surface mismatch and disorder in the superconductor, Phys. Rev. B 106, 085429 (2022).
  * de Moor  _et al._ [2018] M. W. de Moor, J. D. Bommer, D. Xu, G. W. Winkler, A. E. Antipov, A. Bargerbos, G. Wang, N. Van Loo, R. L. O. het Veld, S. Gazibegovic, _et al._ , Electric field tunable superconductor-semiconductor coupling in majorana nanowires, New Journal of Physics 20, 103049 (2018).
  * Kjaergaard  _et al._ [2016] M. Kjaergaard, F. Nichele, H. Suominen, M. Nowak, M. Wimmer, A. Akhmerov, J. Folk, K. Flensberg, J. Shabani, C. Palmstrøm, and C. Marcus, Quantized conductance doubling and hard gap in a two-dimensional semiconductor-superconductor heterostructure, Nature communications 7, 12841 (2016).

See pages 1 of SM.pdf See pages 2 of SM.pdf See pages 3 of SM.pdf See pages 4
of SM.pdf See pages 5 of SM.pdf See pages 6 of SM.pdf


# Quantum Enhanced Pattern Search Optimization

Colton Mikes  Ismael R. de Farias Jr  David Huckleberry Gutman  Victoria E.
Howle  Texas Tech University, Lubbock, TX 91125, USA

###### Abstract

This paper introduces a quantum-classical hybrid algorithm for generalized
pattern search (GPS) algorithms. We introduce a quantum search step algorithm
using amplitude amplification, which reduces the number of oracle calls needed
during the search step from $\mathcal{O}\left(N\right)$ classical calls to
$\mathcal{O}\left(\sqrt{N}\right)$ quantum calls. This work addresses three
fundamental issues with using a quantum search step with GPS. First we address
the need to mark an improved mesh point, a requirement of the amplitude
amplification algorithm. Second, we introduce a modified version of the
amplitude amplification algorithm QSearch, which is guaranteed to terminate
using a finite number of iterations. Third, we avoid disrupting the GPS
algorithm’s convergence by limiting the quantum algorithm to the search step.

##  1 Introduction

Traditional optimization algorithms rely on derivatives to obtain their
results. However, in many cases derivative information may be unavailable.
Even if derivatives of some order exists, it may be impractical or
prohibitively expensive to calculate any of them. For example, it can be
impractical to obtain gradient information when the objective function is
computed using a black-box simulation. Similarly, approximation methods such
as finite differences become prohibitively expensive for objective functions
that are noisy or expensive to calculate. Even for functions constructed
recursively from elementary functions using composition and arithmetic
operations, gradient computation may incur onerous costs in time and memory.
Automatic differentiation can also be used to obtain gradient information in
some cases, but is not always practical since it needs the source code for the
function to be available. In these situations we turn to derivative-free
optimization (DFO) algorithms. DFO algorithms seek to solve a given
optimization problem without the use of differential information of any order.
Instead they rely on calls to a given oracle to evaluate the objective
function. These calls are often expensive and become the dominant cost of the
algorithm.

In this work, we are concerned with a class of DFO algorithms known as
Generalized Pattern Search (GPS). These algorithms generate a sequence of
iterates with non-increasing objective function values by systematically
selecting points to be evaluated and considered for the next iterate. This
process is split into two steps, the search step, and the poll step. The only
difference between them is the points which are evaluated. The search step is
designed to allow for a great amount of flexibility in selecting which points
to consider, while the poll step considers only those points which are needed
to guarantee the algorithm will converge. A typical iteration will begin with
the search step. The poll step is invoked only if the search step fails to
produce an iterate with a reduced objective function value. Since the poll
step is not always necessary, the cost of implementing a GPS algorithm is
often dominated by the search step. However, the various convergence results
introduced by Audet and Dennis make no assumptions about the search step [2,
Theorems 3.7, 3.9, 3.14 and Corollaries 3.11, 3.12, 3.16].

The main contribution of this paper is a quantum algorithm which is able to
perform the search step using $\mathcal{O}\left(\sqrt{N}\right)$ calls to a
quantum oracle, compared to the $\mathcal{O}\left(N\right)$ needed using a
classical oracle. As in [6],[7], and [3], we follow the standard practice of
assuming that the difference in computational cost of a quantum and classical
oracle call is negligible. Our algorithm may be separated into two components:
a modified version of the amplitude amplification algorithm QSearch [4], and a
quantum algorithm, which uses a quantum oracle to prepare the necessary inputs
for our modified QSearch algorithm.

The idea of using amplitude amplification to accelerate GPS algorithms was
previously touched on by Arunachalam in [1]. However, in that work they failed
to address the problems of marking points that provide a reduction in
objective function value, how to guarantee that amplitude amplification will
terminate in a finite number of steps, and how to ensure convergence with the
probability of error introduced by the quantum step. In this paper, we address
all three of these problems. Our algorithm uses a quantum oracle as part of a
subroutine for marking the points which provide a reduction in objective
value; it is guaranteed to terminate in a finite number of steps and preserves
the original algorithm’s convergence properties by performing the poll step on
a classical computer.

The rest of this paper is organized as follows. In section 2, we review GPS
algorithms, quantum computing, and how to represent our optimization problem
using a quantum computer. In section 3, we introduce a modified version of the
amplitude amplification algorithm QSearch [4, Theorem 3]. In section 3.1, we
discuss amplitude amplification and the original QSearch algorithm. In section
3.2, we introduce the modifications needed to ensure QSearch will terminate
using a finite number of iterations. In section 4, we discuss our main
product, the quantum search step algorithm. In section 4.1, we develop the
components needed to use our modified QSearch algorithm to perform the search
step of a GPS algorithm. In section 4.2, we discuss the advantages of using
the quantum search step algorithm over classical methods. We end the paper
with some concluding remarks in section 5.

##  2 Preliminaries

In this section, we review all of the technology and notation from GPS
algorithms and quantum computing required to understand this paper’s main
developments. In section 2.1, we review GPS algorithms, following the
formulation presented in by Audet and Dennis in [2]. In the original
formulation introduced by Torczon in [9], the search and poll steps were not
treated as distinct entities. By separating an iteration into the search and
poll steps, Audet and Dennis were able to show that the search step may
provide increased flexibility, while convergence is guaranteed by the poll
step. In section 2.2, we review some of the fundamental components of quantum
computing, with an eye toward the ingredients necessary to represent our
optimization problem on a quantum computer.

###  2.1 Generalized Pattern Search Algorithms

In this section, we review the construction of GPS algorithms. These
algorithms were originally introduced by Torczon in [9] and expanded on by
Audet and Dennis in [2]. Here we follow Audet and Dennis’s formulation, where
iterations are separated into distinct search and poll steps, so that we may
accelerate the search step, without losing the guarantee of convergence
provided by the poll step.

GPS algorithms solve the optimization problem

$\min_{x\in\mathbb{R}^{n}}f\left(x\right)$ (1)

for some $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, by generating a sequence of
iterates $\left\\{x_{k}\right\\}_{k=0}^{\infty}$ such that
$\left\\{f\left(x_{k}\right)\right\\}_{k=0}^{\infty}$ is a non-increasing
sequence. Each iteration consists of two phases, the search step and the poll
step.

In the search step, we evaluate $f$ at a finite number of points from a set
called the mesh. At the $k$th iteration, the mesh is the set defined by

$M_{k}=\\{x_{k}+\Delta_{k}Dz:z\in\mathbb{N}^{p}\\},$ (2)

where $x_{k}$ is our current iterate, $\Delta_{k}$ is a positive real number
called the mesh size parameter, $D$ is a real valued $n\times p$ matrix whose
columns form a positive spanning set, i.e. every vector in $\mathbb{R}^{n}$
can be written as a non-negative linear combination of $D$’s columns.
Additionally, $D$ satisfies the restriction that its columns are the products
of some non-singular generating matrix $G\in\mathbb{R}^{n\times n}$ and
integer vectors $z_{j}\in\mathbb{Z}^{n}$ for $j=1,2,\ldots,p$. Symbolically,
this restriction means $D$ takes the form $D=\left[Gz_{1}\ldots
Gz_{p}\right]$. At iteration $k$, we call a point $y\in M_{k}$ a improved mesh
point if $f\left(x_{k}\right)>f\left(y\right)$. If such a point is found
during the search step, we end the iteration. Otherwise we begin the poll
step.

During the $k$th iteration, a subset of the columns of $D$ is selected,
denoted by $D_{k}$, which is a positive spanning set. The poll set $P_{k}$ is
formed using the current iterate and the elements of $D_{k}$:

$P_{k}=\\{x_{k}+\Delta_{k}d:d\in D_{k}\\}.$ (3)

If the search step fails, we invoke a poll step, in which we evaluate the
objective function for each of the elements in $P_{k}$ to check for an
improved mesh point. If none are found, we call the current iterate $x_{k}$ a
mesh local optimizer.

Whenever a point $y$ is identified as an improved mesh point by either the
search or poll steps, we immediately end the iteration, set $x_{k+1}=y$, and
either increase or maintain the mesh size parameter. Alternatively, if $x_{k}$
is determined to be a mesh local optimizer, then we set $x_{k+1}=x_{k}$ and
shrink the mesh size parameter. We refer interested readers to [2] for a more
detailed presentation of this version of the GPS algorithm.

###  2.2 Quantum Computing

In this section, we review the relevant basics of quantum computing, and
discuss how to represent our optimization problem (1) on a quantum computer.
As its name implies, a quantum computer is a computational device that
achieves its results by manipulating quantum mechanical systems. At any given
time, the state of a quantum computer can be described by a unit vector,
called the state vector, in a complex valued inner product space. We store
this vector using qubits, the fundamental unit of quantum computation. The
state of an arbitrary qubit may be written as
$\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$, for $\alpha,\beta\in\mathbb{C}$,
where $\left\\{\ket{0},\ket{1}\right\\}$ is the standard basis for
$\mathbb{C}^{2}$, referred to as the computational basis for a single qubit,
denoted here by $\mathcal{C}\left(1\right)$. For those more familiar with non-
physical mathematical notation, we note that $\ket{0}=\left(1,0\right)^{T}$
and $\ket{1}=\left(0,1\right)^{T}$. Since $\ket{\phi}$ must be a unit vector,
we require that $\|\alpha\|^{2}+\|\beta\|^{2}=1$. We call $\alpha$ and $\beta$
the amplitudes of $\ket{\phi}$.

For quantum computers that contain multiple distinct qubits, the state vector
may be obtained by taking the Kronecker product of the qubits. The
computational basis for a quantum computer with $2$ qubits,
$\mathcal{C}\left(2\right)$, is the Kronecker products of the elements in
$\mathcal{C}\left(1\right)$ with each other. In general, the computational
basis of a quantum computer with $N$ qubits, $\mathcal{C}\left(N\right)$, is
the Kronecker products of all the elements in $\mathcal{C}\left(N-1\right)$
and $\mathcal{C}\left(1\right)$. For two arbitrary qubits $\ket{\phi}$ and
$\ket{\theta}$, we write the composite state as
$\ket{\phi}\ket{\theta}=\ket{\phi\theta}$. For a quantum computer with $N$
qubits, all in the same arbitrary state $\ket{\phi}$, we denote the state
vector as $\ket{\phi}^{\otimes N}$. Additionally, when we have a quantum
computer with $N$ qubits, all in the same state from
$\mathcal{C}\left(1\right)$ , we often omit the superscript entirely and write
the state as $\ket{0}$ or $\ket{1}$, so long as the number of qubits is clear
from context. We define a given set of qubits as a quantum register. A set of
qubits is said to be entangled if their state vector cannot be written as the
Kronecker product of single qubit states. Quantum logic gates are modeled as
unitary matrices, which may be applied to the state vector.

An import aspect of quantum mechanics is that we cannot view the state vector
directly. All attempts to do so will produce one of the basis vectors instead.
This action is known as measurement. The results of measurement are determined
by the amplitudes of the state vector. If more than one of the amplitudes are
non-zero, we say that the state vector is in a superposition of the
corresponding states. For example, the probability of obtaining $\ket{0}$ upon
measuring the qubit $\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$ is
$\|\alpha\|_{2}^{2}$, similarly, the probability of obtaining $\ket{1}$ is
$\|\beta\|_{2}^{2}$. If $\alpha$ and $\beta$ are both non-zero, we say that
$\ket{\phi}$ is in a superposition of $\ket{0}$ and $\ket{1}$. A quantum
algorithm is defined as a unitary matrix applied to the state vector, possibly
followed by measurement. If no measurement occurs, we call the quantum
algorithm measurement-free. For quantum computers with multiple qubits,
measurement is performed on each qubit individually. In some circumstances, it
is advantageous to only measure a select few of the qubits. For example,
algorithms such as the swap test [5] rely on measuring a single qubit, and
using the results of that measurement to obtain information on the resulting
state vector.

We now discuss how to represent our optimization problem on a quantum
computer. We represent an arbitrary real number, up to $d$ bits of precision,
using a fixed-point Two’s Complement binary representation. The Two’s
Complement representation is among the most common ways to represent signed
binary numbers. In this representation, the most significant bit represents
the sign of a given binary number. If this bit is $0$, the number is positive.
If it is $1$, it is negative. The negation of a given number is obtained by
flipping each of the bits in its representation and then adding $1$.

For $x\in\mathbb{R}^{n}$, we write $x$ as $dn$ bit binary string, where each
element is represented up to $d$ bits of precision, and the $kth$ set of $d$
bits in the string is the $d$ bit fixed-point representation of the $kth$
element of $x$. Thus $x$ is encoded into $dn$ qubits, where the state of the
$k$th qubit is determined by the $k$th bit of $x$. For example, if $x=0110$,
then $\ket{x}=\ket{0110}$. To evaluate the objective function $f$, we assume
access to a quantum oracle $F$, such that $F\ket{x}\ket{0}^{\otimes n\cdot
d}\rightarrow\ket{x}\ket{f\left(x\right)}$. We may use a single call to the
oracle $F$ to evaluate the objective function for a set of points
$\left\\{x_{j}\right\\}_{j=0}^{m-1}$. This is achieved by first initializing a
quantum register in a superposition of the points and applying $F$,

$F\sum\limits_{j=0}^{m-1}\ket{x_{j}}\ket{0}\rightarrow\sum\limits_{j=0}^{m-1}\ket{x_{j}}\ket{f\left(x_{j}\right)}.$

However, since the function evaluations are stored as a superposition, we
cannot view them directly. In the following sections, we will introduce the
tools necessary for using $F$ to identify reduced objective function values.

##  3 Modified QSearch

In this section, we introduce a modified version of the amplitude
amplification method QSearch introduced in [4, Theorem 3]. If a quantum
computer is in a superposition of desired and undesired states, the QSearch
algorithm may be used to obtain a desired state upon measurement. The need for
our modification arises from the fact that QSearch is not guaranteed to
terminate if there are no desired states in the superposition. The modified
QSearch algorithm will terminate once the probability of the superposition
containing a desired state is sufficiently low. In section 3.1, we review the
core concepts of amplitude amplification and the original QSearch algorithm.
In section 3.2, we introduce a method for determining when the probability of
the superposition containing a desired result has fallen below an arbitrary
tolerance value.

###  3.1 Amplitude Amplification

In this section, we show how the amplitude amplification algorithm QSearch [4,
Theorem 3] can be used to perform the search step of a GPS algorithm. We begin
with a brief review of the algorithm itself.

Suppose we have a measurement-free quantum algorithm $\mathcal{A}$.
Furthermore, suppose that when $\mathcal{A}$ is applied to the initial state
$\ket{0}^{\otimes N}$, the result is a superposition of computational basis
states in $\mathcal{C}\left(N\right)$ some of which are called desired states
($\mathcal{D}$) and others which are called undesired states ($\mathcal{U}$).
More formally, we assume that

$\mathcal{A}\ket{0}=\sum_{\ket{j}\in\mathcal{D}}\alpha_{j}\ket{j}+\sum_{\ket{k}\in\mathcal{U}}\alpha_{k}\ket{k}$
(4)

where $\mathcal{D},\mathcal{U}\subseteq\mathcal{C}\left(N\right)$ with
$\mathcal{D}\cap\mathcal{U}=\emptyset$ and

$\sum_{\ket{j}\in\mathcal{D}}|\alpha_{j}|^{2}+\sum_{\ket{k}\in\mathcal{U}}|\alpha_{k}|^{2}=1.$

Amplitude amplification methods are a class of quantum algorithms designed to
increase the probability of obtaining a desired state upon measurement.
Introduced in [4], the authors developed multiple amplitude amplification
algorithms, each of which make different assumptions on both the number of
desired states and the user’s knowledge of this number.

For our purposes, we wish to be able to apply amplitude amplification when
there may be an arbitrary (possibly $0$) number of desired states, and the
user has no knowledge of this number. The assumptions made by QSearch are the
closest to satisfying these requirements. Qsearch assumes there is at least
one desired state, but that the actual number of desired states is unknown. It
works by constructing the measurement-free quantum algorithm $Q$, which can be
repeatedly applied to increase the probability of obtaining a desired state
upon measurement. We define $Q$ as
$Q=-\mathcal{A}S_{0}\mathcal{A}^{-1}S_{\chi}$, where

  * •

$\mathcal{A}^{-1}$ is the quantum algorithm obtained by taking the inverse of
$\mathcal{A}$.

  * •

$S_{0}$ is the measurement-free quantum algorithm, which acts as the identity
for all computational basis states other than $\ket{0}^{\otimes N}$, and
$S_{0}\ket{0}^{\otimes N}=-\ket{0}^{\otimes N}$. Thus for
$\ket{x}\in\mathcal{C}\left(N\right)$

$S_{0}\ket{x}=\begin{cases}-\ket{x}&\text{if }\ket{x}=\ket{0}^{\otimes N}\\\
\ket{x}&\text{if }\ket{x}\neq\ket{0}^{\otimes N}\\\ \end{cases}$

  * •

$S_{\chi}$ is the measurement-free quantum algorithm that flips the sign of
desired computational basis states. Thus for
$\ket{x}\in\mathcal{C}\left(N\right)$

$S_{\chi}\ket{x}=\begin{cases}-\ket{x}&\text{if }\ket{x}\in\mathcal{D}\\\
\ket{x}&\text{if }\ket{x}\in\mathcal{C}\left(N\right)\setminus\mathcal{D}\\\
\end{cases}$

With our main ingredient in hand, the quantum algorithm $Q$, we are equipped
to formally state the QSearch algorithm.

Algorithm 1 QSearch

Input: A measurement-free quantum algorithm $\mathcal{A}$, which operates on
$N$ qubits, $S_{0}$ and $S_{\chi}$ as defined above, and a quantum state
composed of $n$ qubits initialized to the state $\ket{0}^{\otimes N}$.

1:Set $l=0$ and let $c$ be any constant such that $1<c<2$.

2:Apply $\mathcal{A}$ to $\ket{0}^{\otimes N}$ and measure. If the result of
measurement is a desired state, then return the state.

3:while A desired state has not been returned do

4: Increase $l$ by 1 and set $M=\lceil c^{l}\rceil$.

5: Initialize a register of appropriate size to the state
$\mathcal{A}\ket{0}^{\otimes N}$.

6: Set $j$ to be an integer in $\left[1,M\right]$ uniformly at random.

7: Apply the algorithm $Q$ to the state $\mathcal{A}\ket{0}^{\otimes N}$ $j$
times.

8: Measure the state. If it is desired, return the state.

9:end while

Output: A desired state.

The following theorem from [4, Theorem 3] elaborates on the number of
applications of $\mathcal{A}$ and $\mathcal{A}^{-1}$ that will be required by
QSearch. For the sake of concision, we refer the reader to [4] for its proof.

######  Theorem 1.

Let $\mathcal{A}$ be a measurement-free quantum algorithm, such that
$\mathcal{A}\ket{0}^{\otimes N}$ may be written as the superposition of $N$
states, $t$ of which are desired. Exactly one of the following cases holds
based on the value of t:

  * •

$t>0$: QSearch will return a desired state using
$\Theta\left(\sqrt{\frac{N}{t}}\right)$ applications of $\mathcal{A}$ and
$\mathcal{A}^{-1}$.

  * •

$t=0$: QSearch will fail to terminate.

Theorem 1 guarantees that if a successful state exists among those being
searched, it will be found using $\Theta\left(\sqrt{N}\right)$ applications of
$\mathcal{A}$. However, if such a state does not exist, the algorithm does not
terminate. To apply QSearch in our setting, we must ensure that it will
terminate, regardless of if a desired state exists or not.

###  3.2 Adding a Stopping Criteria to QSearch

In this section, we introduce a stopping criteria to be used in our modified
QSearch. This criteria will allow for an arbitrarily low probability of
terminating the algorithm when a desired state exists.

Suppose we have access to a measurement-free quantum algorithm $\mathcal{A}$
such that $\mathcal{A}\ket{0}^{\otimes N}$ may be written as a superposition
of $N$ states, $t$ of which are desired. As stated in theorem 1, if $t=0$,
then QSearch will fail to terminate. Unless we measure each of the $N$ states,
it is impossible to know for certain that $t=0$. However, we can bound the
probability of $t>0$ using our knowledge of $N$ and the number of iterations
of QSearch that have been performed. Suppose $0<\frac{t}{N}<\frac{3}{4}$, and
$M$ is some integer such that $M>\sqrt{N}$. Then as shown in the proof of [4,
Theorem 3], if we apply $Q$, $j$ times, where the integer $j$ is chosen from
$\left[1,M\right]$ uniformly at random, then the probability of obtaining a
desired state is bounded below by

$\frac{1}{2}\left(1-\frac{1}{2M\sqrt{\frac{t}{N}}}\right).$ (5)

We use this knowledge to prove the following lemma:

######  Lemma 2.

Suppose we have access to a measurement-free quantum algorithm $\mathcal{A}$
such that $\mathcal{A}\ket{0}^{\otimes N}$ may be written as a superposition
of $N$ states, $t$ of which are desired. Let $M\in\mathbb{Z},M>\sqrt{N}$, and
$j\in\mathbb{Z}$ is an integer chosen from $\left[1,M\right]$ uniformly at
random. If $0<\frac{t}{N}<\frac{3}{4}$ and we have applied $u$ iterations of
QSearch, each failing to produce a desired state, then the probability of
failing to find a desired state on the next iteration of QSearch is bounded
above by $\left(\frac{3}{4}\right)^{u}$.

###### Proof.

In the course of proving Theorem 1 ([4, Theorem 3]), [4] shows that if we
apply $Q$, $j$ times, then the probability of obtaining a desired state is
bounded below by $\frac{1}{2}\left(1-\frac{1}{2M\sqrt{\frac{t}{N}}}\right)$.
Since we do not know the value of $t$ ahead of time, we assume the worst case
of $t=1$ and reduce this bound to obtain our result.

$\begin{split}\frac{1}{2}\left(1-\frac{1}{2M\sqrt{\frac{t}{N}}}\right)&=\frac{1}{2}\left(1-\frac{\sqrt{N}}{2M\sqrt{t}}\right)\\\
&\geq\frac{1}{2}\left(1-\frac{\sqrt{N}}{2M}\right).\end{split}$

For $M>\sqrt{N}$ we have

$\frac{1}{2}\left(1-\frac{\sqrt{N}}{2M}\right)>\frac{1}{4}.$

Thus the probability of failing to find a desired state is bounded above by
$\frac{3}{4}$. Since each iteration of QSearch is independent, the probability
of failing to find a desired state during $u$ iterations of QSearch is bounded
above by $\left(\frac{3}{4}\right)^{u}$. ∎

Using Lemma 2, we can determine when the probability of missing an existing
desired solution has fallen below an arbitrary tolerance value. We now have
the tools necessary for the introduction of our modified QSearch algorithm.

Algorithm 2 Modified QSearch

Input: A measurement-free quantum algorithm $\mathcal{A}$, which operates on
$N$ qubits, $S_{0}$ and $S_{\chi}$ as defined above, a tolerance value
$\tau>0$, and a quantum state composed of n qubits initialized to the state
$\ket{0}^{\otimes N}$.

1:Set $l=0$ and let $c$ be any constant such that $1<c<2$.

2:Set $u$ = 0.

3:Apply $\mathcal{A}$ to $\ket{0}^{\otimes N}$ and measure. If the result of
measurement is a desired state, then return the state.

4:while A desired state has not been returned and
$u<\frac{\ln\left(\tau\right)}{\ln\left(\frac{3}{4}\right)}$ do

5: Increase $l$ by 1 and set $M=\lceil c^{l}\rceil$.

6: if $M>\sqrt{N}$ then

7: Set $u=u+1$.

8: end if

9: Initialize a register of appropriate size to the state
$\mathcal{A}\ket{0}^{\otimes N}$.

10: Set $j$ to be an integer in $\left[1,M\right]$ uniformly at random.

11: Apply the algorithm $Q$ to the state $\mathcal{A}\ket{0}^{\otimes N}$ $j$
times.

12: Measure the state. If it is desired, return the desired state.

13:end while

14:If a desired state was not found, return the failure to find a desired
state.

Output: A desired state or failure to find a desired state.

With our modified QSearch algorithm introduced, we now show how it may be used
to perform the search step of a given GPS algorithm.

##  4 The Quantum Search Step

In this section, we introduce our main product, the quantum search step
algorithm. This algorithm completes the search step of a given GPS algorithm
using $\mathcal{O}\left(\sqrt{N}\right)$ quantum oracle calls, compared to the
$\mathcal{O}\left(N\right)$ classical oracle calls. Here we follow the
standard assumption that the computational cost between quantum and classical
oracle calls is negligible [6],[7],[3]. Let
$X=\left\\{x_{j}\right\\}_{j=0}^{N-1}$. Recall that we represent $x\in X$ as a
$dn$ binary string, where the $k$th set of $d$ bits represents the $k$th
element of the point. For a given objective function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, we assume access to a quantum oracle
$F$, which is able to implement the transformation

$F\sum\limits_{j=0}^{N-1}\ket{x_{j}}\ket{0}\rightarrow\sum\limits_{j=0}^{N-1}\ket{x_{j}}\ket{f\left(x_{j}\right)}.$

In section 4.1 we show how to implement the operator $Q$ needed to use the
modified QSearch algorithm before formally stating the quantum search step
algorithm. In section 4.2, we discuss the advantages of using the quantum
search step algorithm over classical methods, how the quantum search step
preserves the original convergence properties of a given GPS algorithm, and
why we choose not to use the modified QSearch algorithm to perform the poll
step.

###  4.1 Preparing the Operator Q

Recall that our goal is to use the modified QSearch algorithm to search for an
improved mesh point among a set of points from a mesh, as described in section
2.1. This application requires that we construct the operator
$Q=\mathcal{A}S_{0}\mathcal{A}^{-1}S_{\chi}$, which is equivalent to
implementing the operators $\mathcal{A}$, $S_{0}$, $\mathcal{A}^{-1}$, and
$S_{\chi}$. In this section, we will show how to implement the following
components of $Q$:

  * •

$\mathcal{A}$, such that $\mathcal{A}\ket{0}^{\otimes N}$ produces a
superposition of the points we wish to search.

  * •

$S_{0}$ is the measurement-free quantum algorithm, which acts as the identity
for all computational basis states other than $\ket{0}^{\otimes N}$, and
$S_{0}\ket{0}^{\otimes N}=-\ket{0}^{\otimes N}$. Thus for
$\ket{x}\in\mathcal{C}\left(N\right)$

$S_{0}\ket{x}=\begin{cases}-\ket{x}&\text{if }\ket{x}=\ket{0}^{\otimes N}\\\
\ket{x}&\text{if }\ket{x}\neq\ket{0}^{\otimes N}\\\ \end{cases}$

  * •

$\mathcal{A}^{-1}$ is the quantum algorithm obtained by taking the inverse of
$\mathcal{A}$.

  * •

$S_{\chi}$ is the measurement-free quantum algorithm that flips the sign of
computational basis states corresponding to improved mesh points. Thus for
$\ket{x}\in\mathcal{C}\left(N\right)$

$S_{\chi}\ket{x}=\begin{cases}-\ket{x}&\text{if }x\text{ is an improved mesh
point}\\\ \ket{x}&\text{if }x\text{ is not an improved mesh point}\\\
\end{cases}$

$S_{\chi}$ presents the greatest challenge for constructing $Q$ since it
requires that we be able to mark improved mesh points. We do this by designing
$\mathcal{A}$ to operate on three quantum registers. The first two are the
same as those used by our oracle $F$. The third register will be used to
compare the objective function value at the current iterate and the points we
wish to search.

Let $X=\left\\{x_{j}\right\\}_{j=0}^{N-1}$ be a set of $N$ points chosen from
the mesh, $f\left(x_{j}\right)=f_{j}$ be the objective function evaluated at
the point $x_{j}$, and $x_{k}$ be the current iterate. We will design
$\mathcal{A}$ such that

$\mathcal{A}\ket{0}=\frac{1}{\sqrt{N}}\sum\limits_{j=0}^{N-1}\ket{x_{j}}\ket{f_{j}}\ket{f_{j}-f_{k}}.$
(6)

The sign qubit of $\ket{f_{j}-f_{k}}$ is then in the state $\ket{1}$ if and
only if $\ket{x_{j}}\ket{f_{j}}\ket{f_{j}-f_{k}}$ is a desired state. We may
use this qubit as a control qubit in our construction of $S_{\chi}$. Our
algorithm $\mathcal{A}$ is then as follows:

Algorithm 3 $\mathcal{A}$

Input: Let $f\left(x_{k}\right)=f_{k}$ be the objective function evaluated at
the current iterate $x_{k}$, and let $X=\left\\{x_{j}\right\\}_{j=0}^{N-1}$ be
a set of $N$ points chosen from the mesh.

1:Place the third register in the state $\ket{-f_{k}}$
$\ket{\phi_{0}}=\ket{0}\ket{0}\ket{-f_{k}}.$

2:Place the first register into a uniform superposition of the $N$ points.
$\ket{\phi_{1}}=\frac{1}{\sqrt{N}}\sum\limits_{j=0}^{N-1}\ket{x_{j}}\ket{0}\ket{-f_{k}}.$

3:Apply the oracle $F$ to the first two registers
$\ket{\phi_{2}}=\frac{1}{\sqrt{N}}\sum\limits_{j=0}^{N-1}\ket{x_{j}}\ket{f_{j}}\ket{f_{k}}.$

4:Add the second register to the third register using the in-place signed qft
addition algorithm introduced in [8, Section 3.1]
$\ket{\phi_{3}}=\frac{1}{\sqrt{N}}\sum\limits_{j=0}^{N-1}\ket{x_{j}}\ket{f_{j}}\ket{f_{j}-f_{k}}.$

Output: $\ket{\phi_{3}}$

In this context, the set of desired and undesired states are naturally given
as

$\displaystyle\mathcal{D}$
$\displaystyle:=\\{\ket{x_{j}}\ket{f_{j}}\ket{f_{j}-f_{k}}:f_{j}-f_{k}<0\\}$
$\displaystyle\mathcal{U}$
$\displaystyle:=\\{\ket{x_{j}}\ket{f_{j}}\ket{f_{j}-f_{k}}:f_{j}-f_{k}\geq
0\\}.$

With $\mathcal{A}$ defined, $\mathcal{A}^{-1}$ is easily obtained by as the
inverse of $\mathcal{A}$. To implement $S_{0}$, we first consider the single
qubit gate defined by the unitary matrix

$U=\begin{bmatrix}-1&0\\\ 0&1\end{bmatrix}.$

The action of this gate on the computational basis is $U\ket{0}=-\ket{0}$ and
$U\ket{1}=\ket{1}$. Thus $U$ acts as $S_{0}$ for a single qubit. However, our
algorithm will always require more than one qubit. We may use $U$ to implement
$S_{0}$ for an arbitrary number of qubits by applying $U$ to the first qubit,
controlled on the remaining qubits being in the state $\ket{0}$.

As with $S_{0}$, we can implement $S_{\chi}$ as a controlled version of a
single qubit gate. Recall that after applying $\mathcal{A}$, the sign qubit of
the comparison register is in the state $\ket{1}$ if the state represents an
improved mesh point, otherwise it is in the state $\ket{0}$. Consider the
single qubit gate represented by the matrix

$V=\begin{bmatrix}e^{i\pi}&0\\\ 0&e^{i\pi}\end{bmatrix}.$

We can implement $S_{\chi}$ by applying $V$ to the first qubit of the input
register, controlled on the sign qubit of the comparison register being in the
state $\ket{1}$. Now that we have a method of preparing all the ingredients of
$Q$, we are prepared to present the quantum search step.

Algorithm 4 The Quantum Search Step

Input: $\mathcal{A}$, $S_{0}$, $\mathcal{A}^{-1}$, and $S_{\chi}$ as defined
above, a set of points to be searched $\left\\{x_{j}\right\\}_{j=0}^{N-1}$,
the current iterate $x_{k}$, a tolerance value $\tau_{0}$ > 0, and three
quantum registers in the state $\ket{\psi}=\ket{0}\ket{0}\ket{0}$.

1:Apply modified QSearch to $\ket{\psi}$.

2:if modified QSearch returns an improved mesh point, $x^{\prime}$ then

3: Set $x_{k+1}=x^{\prime}$ and update the mesh size parameter.

4:elseterminate the algorithm and return the failure to find an improved mesh
point.

5:end if

Output: The next iterate $x_{k+1}$, or failure to find an improved mesh point.

With the quantum search step in hand, we now discuss its effect on convergence
and how it compares to classical methods.

###  4.2 Convergence and the Quantum Advantage

In this section, we discuss the effects modified QSearch may have on the
convergence properties of GPS algorithms as well as the advantages of the
quantum search step compared to classical methods.

It is worthwhile to note that the only difference between the search step and
the poll step is the set of points that are considered. The motivation for
separating an iteration into these steps is the unique roll they each fill
within a given GPS algorithm. The search step allows for a much wider and more
varied selection of points from the mesh. This is because it places very few
restrictions on which points are to be considered. They must each each come
from a given mesh, and the total number of points must be finite. This allows
an impressive level of flexibility when deciding how to implement the search
step. In practice, this flexibility is key to the effectiveness of GPS
algorithms [2]. However, this flexibility also prevents the search step from
being sufficient to guarantee the algorithm will converge. This is the roll of
the poll step. In [2, Theorems 3.7, 3.9, 3.14 and Corollaries 3.11, 3.12,
3.16], Audet and Dennis present a variety of different convergence results,
each differing in it’s assumptions about the objective function. However,
while these results all assume the poll step is performed as described in
section 2.1. However, they make no assumptions about the search step. Thus we
can think of the poll step as an extra step to ensure the algorithm will
converge. This is why we restrict our use of modified QSearch to the search
step. While we may ensure that the probability of overlooking an improved mesh
point is arbitrarily low, we cannot ensure it is $0$ without increasing our
oracle calls to $\mathcal{O}\left(N\right)$.

Suppose we wish to consider $N$ points from the mesh. Classical methods
require $\mathcal{O}\left(N\right)$ oracle calls to complete the search step.
However, the quantum search step can search the same $N$ points using
$\mathcal{O}\left(\sqrt{N}\right)$ oracle calls. We now conclude this section
by summarizing the advantages of the quantum search step in the following
theorem,

######  Theorem 3.

Let $X$ be a set of $N$ points chosen from the mesh, $t$ of which are improved
mesh points. Exactly one of the following cases will hold

  * •

The quantum search step will return an improved mesh point using
$\Theta\left(\sqrt{\frac{N}{t}}\right)$ calls to the quantum oracle.

  * •

The quantum search step will terminate without finding the next iterate.

If $X$ contains an improved mesh point, the probability of the quantum search
step terminating without finding the next iterate may be set arbitrarily low.

###### Proof.

If the quantum search step returns an improved mesh point, Theorem 1
guarantees that it will do so using $\Theta\left(\sqrt{\frac{N}{t}}\right)$
calls to the quantum oracle.

Suppose the algorithm terminates without producing the next iterate and $X$
contains an improved mesh point. By Lemma 2, the probability of failing to
find an improved mesh point on the next iteration is bounded above by
$\left(\frac{3}{4}\right)^{u}$, where $u$ is the number of iterations of
modified QSearch performed after $M>\sqrt{N}$. Thus for $\tau>0$, if
$u<\frac{\ln\left(\tau\right)}{\ln\left(\frac{3}{4}\right)}$, then

$\begin{split}u&<\frac{\ln\left(\tau\right)}{\ln\left(\frac{3}{4}\right)}\\\
uln\left(\frac{3}{4}\right)&<ln\left(\tau\right)\\\
ln\left(\left(\frac{3}{4}\right)^{u}\right)&<ln\left(\tau\right)\\\
\left(\frac{3}{4}\right)^{u}&<\tau\end{split}$

and we have that the probability of the quantum search step failing to find an
improved mesh point on the next iteration is less than $\tau$. ∎

##  5 Concluding Remarks

In this work, we introduced a modified version of the amplitude amplification
algorithm QSearch [4, Theorem 3]. Our modified QSearch guarantees that the
algorithm will terminate using a finite number of steps, with an arbitrarily
low probability of failing to produce a desired state, if one exists. We then
showed how modified QSearch can be used to implement the quantum search step,
a quantum algorithm for performing the search step of a given GPS algorithm.
When searching $N$ points, $t$ of which are improved mesh points, our
algorithm is able to complete the search step using
$\mathcal{O}\left(\sqrt{N}\right)$ quantum oracle calls, compared to the
$\mathcal{O}\left(N\right)$ classical oracle calls needed traditionally. If
$t>0$, our quantum search step has an arbitrarily low probability of failing
to identify an improved mesh point.

## References

  * [1] Srinivasan Arunachalam.  Quantum speed-ups for boolean satisfiability and derivative-free optimization.  Master’s thesis, University of Waterloo, 2014.
  * [2] Charles Audet and J. E. Dennis.  Analysis of generalized pattern searches.  SIAM Journal on Optimization, 13(3):889–903, 2002.
  * [3] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  SIAM Journal on Computing, 26(5):1411–1473, 1997.
  * [4] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Quantum Computation and Information, page 53–74, 2002.
  * [5] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87(16):167902, 2001.
  * [6] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe.  Optimizing quantum optimization algorithms via faster quantum gradient computation.  ArXiv, abs/1711.00465, 2017.
  * [7] Stephen P. Jordan.  Fast quantum algorithm for numerical gradient estimation.  Phys. Rev. Lett., 95:050501, 2005.
  * [8] Engin Sahin.  Quantum arithmetic operations based on quantum Fourier transform on signed integers.  International Journal of Quantum Information, 18(06):2050035, 2020\.
  * [9] Virginia Torczon.  On the convergence of pattern search algorithms.  SIAM Journal on Optimization, 7(1):1–25, 1997.


[a]Anton V. Sokolov

# Magnetic anomaly coefficients for QCD axion couplings

Andreas Ringwald

###### Abstract

We argue that there are both experimental and theoretical reasons to
reconsider the construction of KSVZ-like axion models. From the experimental
side, predictions for the axion-photon coupling are not consistent with the
collection of astrophysical hints. From the theoretical side, we find that the
construction can be conceptually simplified. In particular, it contains an
unnecessary assumption on the type of the gauge theory involved which has far-
reaching consequences for low energy axion phenomenology. In order to relax
this assumption, we allow heavy fermions of the KSVZ-like models to carry
magnetic charge. We then show that the axion-photon coupling is generically
dominated by the axial anomaly of magnetic currents. Finally, we derive the
expression for magnetic anomaly coefficients, which determine the range of
numerical values for the axion-photon coupling.

DESY 21-140

##  1 Motivation

Axions are pseudo Nambu-Goldstone bosons of the spontaneously broken anomalous
global $U(1)_{\text{PQ}}$ symmetry [1, 2, 3, 4]. They are one of the best
motivated hypothesised particles beyond the Standard model. Not only do axions
provide an attractive dynamical solution to the strong CP problem, but they
are also perfect candidates to account for the cold dark matter abundance
suggested by astrophysical and cosmological observations [5, 6, 7]. There is a
vast number of ideas how one can potentially discover axions, both directly in
the laboratory and indirectly through astrophysical data. Many of them have
been already put into practice and more are yet to be implemented in the
future. Although the axion has not been discovered so far, its parameter space
has been constrained and even some hints pointing to a particular range of
parameters have been found. Since most of the axion searches exploit
especially its coupling to photons, it is very important to understand which
values of this coupling are theoretically preferred. In the conventionally
used axion models, which are KSVZ- and DFSZ-like models [8, 9, 10, 11], it is
predicted that on a plot of axion-photon coupling versus axion mass the
relevant values occupy a band, see fig. 2. There are however reasons, both
experimental and theoretical, to question the relevance of this band. From the
experimental side, there are astrophysical hints, associated to the cooling of
horizontal branch stars in globular clusters [12] and anomalous TeV-
transparency of the Universe [13, 14, 15], which agree among each other and
after being combined point to a parameter region far above the conventional
axion band. From the theoretical side, we find that there is an unjustified
assumption entering the construction of the KSVZ-like models, which influences
drastically predicted values for the axion-photon coupling. After relaxing
this assumption, one arrives at a conceptually simpler model, which we analyse
in this work. What we find is that, quite intriguingly, the phenomenology of
the latter minimal model does agree with the astrophysical hints mentioned
earlier, thus resolving the existing controversy between theory and
experiment.

Our narration proceeds as follows. In sec. 2, we show how one can conceptually
simplify the construction of the KSVZ-like models by relaxing an assumption on
the type of the gauge theory involved. In sec. 3, we explore the phenomenology
of the resulting model by relating axion effective field theory operators to
the expression for the axial anomaly in a generic Abelian gauge theory, where
both electric and magnetic gauge charges are allowed.

##  2 KSVZ-like models are intrinsically biased

Normally, construction of the KSVZ-like axion models proceeds as follows. One
introduces a complex scalar field $\Phi$, which breaks the $U(1)_{\text{PQ}}$
symmetry spontaneously after relaxing to its non-zero vacuum expectation value
$v_{a}/\sqrt{2}$. For consistency with observations, $v_{a}$ must correspond
to some high energy scale. Moreover, in order to solve the strong CP problem,
the $U(1)_{\text{PQ}}$ symmetry has to be color anomalous. This is achieved
via introducing a new vector-like colored fermion $\psi=\psi_{L}+\psi_{R}$, so
that $U(1)_{\text{PQ}}$ acts differently on the two chirality components of
$\psi$. These requirements lead naturally to the following Lagrangian:

$\mathcal{L}\;\supset\;i\bar{\psi}\gamma^{\mu}D_{\mu}\psi+y\left(\Phi\,\bar{\psi}_{L}{\psi}_{R}+\text{h.c.}\,\right)-\lambda_{\Phi}\left(\left|\Phi\right|^{2}-\frac{v_{a}^{2}}{2}\right)^{\\!\\!2},$
(1)

where $y$ and $\lambda_{\Phi}$ are some dimensionless constants and $D_{\mu}$
is a covariant derivative encoding the interaction of $\psi$ with the gauge
fields of the Standard model. Note that as a result of the spontaneous
symmetry breaking $\psi$ gets a mass $m=yv_{a}/\sqrt{2}$, which is very large
for reasonable values of $y$. What remains as a low energy degree of freedom
is a pseudo Nambu-Goldstone boson of the spontaneous symmetry breaking $a$ –
the axion – which can be thought of as an angular mode of $\Phi$. The axion
interacts with the gauge fields of the Standard model through loops of $\psi$.
In particular, at low energies, where the relevant gauge bosons are photons
and gluons, these interactions are given by the axion field times the
expressions for axial electromagnetic and color anomalies, respectively, with
some coefficients:

$\mathcal{L}_{a}\;\supset\;-\frac{1}{4}\,g^{0}_{a\gamma\gamma}\,a\,F_{\mu\nu}\tilde{F}^{\mu\nu}\,+\,\frac{ag_{s}^{2}}{32\pi^{2}f_{a}}\;G_{\mu\nu}^{a}\tilde{G}^{a\,\mu\nu}\,,\quad
f_{a}=\frac{v_{a}}{2N}\,,\quad
g^{0}_{a\gamma\gamma}=\frac{E}{N}\cdot\frac{e^{2}}{8\pi^{2}f_{a}}\,.$ (2)

The parameters $E$ and $N$ are called electromagnetic and color anomaly
coefficients, respectively. They depend on the representation of $\psi$ under
the gauge symmetries of the Standard model. Since the latter representation is
unknown, $E$ and $N$ can in principle vary considerably, which gives rise to
an uncertainty in the parameter $g^{0}_{a\gamma\gamma}$ [16]. This uncertainty
translates into a band on the plot of possible axion-photon couplings
$g_{a\gamma\gamma}$ versus axion mass $m_{a}$, see fig. 2, due to the
following relations111$m_{u},m_{d},m_{\pi}$ are masses of u-quark, d-quark and
pion, respectively; $f_{\pi}$ is pion decay constant.:

$g_{a\gamma\gamma}\;=\;g^{0}_{a\gamma\gamma}-\frac{e^{2}}{12\pi^{2}f_{a}}\cdot\frac{4m_{d}+m_{u}}{m_{u}+m_{d}}\,,\quad
m_{a}=\frac{m_{\pi}f_{\pi}\sqrt{m_{u}m_{d}}}{\left(m_{u}+m_{d}\right)f_{a}}\,.$
(3)

Let us now elaborate why the construction presented in the previous paragraph
contains an implicit far-reaching assumption. While allowing the new heavy
fermion $\psi$ to be charged under any possible gauge symmetry at hand is
indeed the most generic option, it is not consistently implemented in the
KSVZ-like models. The reason is that these models consider only electric
representations of the gauge groups. Meanwhile, as it was shown back in 1931
by Dirac [17], gauge interactions in the quantum theory need not be limited to
the electric ones: gauge charges can be electric as well as magnetic. Although
we do not see magnetic charges at low energies, their existence is actually
indirectly evidenced by the quantization of the electric charge observed in
nature. Indeed, as Dirac found, quantum theory requires that the electric
gauge charge $e$ is related to the magnetic one $g$ as follows: $eg=2\pi
n\,,n\in\mathbb{Z}$, so that the charges are quantized. Moreover, as it was
advocated in ref. [18], there is a mounting evidence supporting the conjecture
that charge quantization is not only a necessary but also a sufficient
condition for the magnetic monopoles to exist. Quantum field theory coupled to
gravity suggests that any possible electric or magnetic charge should have a
physical realization. The construction of KSVZ-like models is thus too
restrictive, so that the gauge charges assigned to the heavy fermion $\psi$
are not generic and the resulting predictions for axion couplings are biased.

##  3 Axion-photon coupling from the axial anomaly of magnetic currents

Let us now relax the above-mentioned assumption on the representations of the
heavy fermion $\psi$ under the gauge groups of the Standard model and consider
a truly generic setting. In this setting, $\psi$ is a dyon, i.e. a particle
carrying both electric and magnetic charges. We limit our investigation to
axion phenomenology at low energies, so that the relevant gauge interactions
are electromagnetic and color ones. For simplicity, we also do not consider
here the case where $\psi$ has a color magnetic charge, which is studied in
detail in our publication [19]. Since this means we do not modify the strong
sector of the model, phenomenology of the strong interactions of axions is
fully analogous to the one in the KSVZ model: in particular, the strong CP
problem is solved and the relation between axion mass $m_{a}$ and decay
constant $f_{a}$ is standard. What is modified are axion-photon interactions.
Let us proceed to derive the latter from the UV theory with the Lagrangian
given by eq. (1). As it was shown by Zwanziger [20], a local quantum field
theory with both electric and magnetic charges necessarily involves two
vector-potentials, $A_{\mu}$ and $B_{\mu}$, each having the standard coupling
to the corresponding current, electric or magnetic, respectively. The
covariant derivative entering eq. (1) is thus
$D_{\mu}=\partial_{\mu}-e_{0}\,q_{e}A_{\mu}-g_{0}\,q_{m}B_{\mu}$, where
$e_{0}=e/3$ and $g_{0}$ are elementary electric and magnetic charges,
respectively. Due to the Dirac quantization condition, $g_{0}=2\pi/e_{0}$.

Below the PQ symmetry breaking scale, one can expand
$\Phi=(v_{a}+\rho)\exp{\left(ia/v_{a}\right)}/\sqrt{2}$, where $\rho$ is a
heavy radial mode and $a$ is a pseudo Nambu-Goldstone boson (axion). The terms
in the resulting Lagrangian which are relevant for the low energy
phenomenology are:

$\mathcal{L}\;\supset\;i\bar{\psi}\gamma^{\mu}D_{\mu}\psi+\frac{yv_{a}}{\sqrt{2}}\left\\{\exp{\left(\frac{ia}{v_{a}}\right)}\,\bar{\psi}_{L}\psi_{R}+\text{h.c.}\right\\}.$
(4)

We perform then an axial rotation of the fermion
$\psi\rightarrow\exp{(ia\gamma_{5}/2v_{a})}\cdot\psi$, after which there arise
an anomalous term $\mathcal{L}_{\text{F}}$ from the transformation of the
measure of the path integral and a derivative coupling of $a$ to the axial
current of $\psi$:

$\mathcal{L}\;\supset\;i\bar{\psi}\gamma^{\mu}D_{\mu}\psi+\frac{yv_{a}}{\sqrt{2}}\,\bar{\psi}\psi-\frac{\partial^{\mu}a}{2v_{a}}\,\bar{\psi}\gamma_{\mu}\gamma_{5}\psi-\mathcal{L}_{\text{F}}\,.$
(5)

The axial anomaly in a theory with dyons was found in ref. [21], from where
one infers the expression for the anomalous term222Although it may naively
seem that the axion shift symmetry $a\rightarrow a+2\pi v_{a}$ forbids some of
the terms in eq. (6), it actually does not, which we elaborate in a
forthcoming paper.:

$\mathcal{L}_{\text{F}}\;=\;\frac{a\cdot
d\\!\left({{C}}_{{\psi}}\right)}{16\pi^{2}v_{a}}\cdot\left\\{\left(e_{0}^{2}q_{e}^{2}-g_{0}^{2}\,q_{m}^{2}\right)F_{\mu\nu}\tilde{F}^{\mu\nu}-4\pi
q_{m}q_{e}F_{\mu\nu}{F}^{\mu\nu}\right\\}.$ (6)

The dimension $d({{C}}_{{\psi}})$ of the color representation of $\psi$ in the
numerator on the right-hand side comes from summing over the color indices. We
corrected a mistake which crawled into the coefficient of the last term on the
right-hand side in the original expression for the anomalous current in ref.
[21]. This term is CP-violating and arises only if there is CP-violation in
the UV theory. A generic theory with dyons does violate CP, unless for any
dyon with charges ($q_{e}$, $q_{m}$) there is another dyon with charges
($q_{e}$, $-q_{m}$). Anyway, be there CP-violation or not, it is easy to see
that the second term on the right-hand side of eq. (6) dominates over all
other terms: if we assume $q_{e},q_{m}\sim 1$, its coefficient is by a factor
of $4\pi^{2}/e_{0}^{4}$ larger than the coefficient in front of the first term
and by a factor of $\pi/e_{0}^{2}\,$ – than the coefficient in front of the
third term. At the leading order, as long as $m=yv_{a}/\sqrt{2}$ is very
large, the derivative axion coupling from eq. (5) does not contribute to the
low energy Lagrangian of axion-photon interactions, for the same reason as in
the KSVZ-like models333The reason is the behaviour of the Ward identities for
the correlation functions which involve the axial current of $\psi$ in the
limit $m\rightarrow\infty$.. The leading effect in the interactions between
axion and photons is thus given by the following Lagrangian:

$\mathcal{L}_{a\gamma}=\frac{1}{4}\,\tilde{g}_{a\gamma\gamma}\,aF_{\mu\nu}\tilde{F}^{\mu\nu},\quad\tilde{g}_{a\gamma\gamma}=\frac{q_{m}^{2}\,d\\!\left(C_{\psi}\right)g_{0}^{2}}{4\pi^{2}v_{a}}\,,$
(7)

where we took into account that the contribution to the axion-photon coupling
$\tilde{g}_{a\gamma\gamma}$ from the strong sector, see eq. (3), is now
absolutely negligible. The axion-photon coupling can be rewritten in terms of
the magnetic anomaly coefficients $\tilde{E}_{\psi}$:

$\tilde{g}_{a\gamma\gamma}=\frac{\tilde{E}}{N}\cdot\frac{g_{0}^{2}}{8\pi^{2}f_{a}}\,,\quad\tilde{E}=\sum_{\psi}\tilde{E}_{\psi}=\sum_{\psi}q_{m}^{2}(\psi)\cdot
d\\!\left(C_{\psi}\right)\,,$ (8)

where $q_{m}(\psi)\in\mathbb{Z}$ are magnetic charges of new heavy fermions
$\psi$. For example, in case of a single new heavy quark $\psi$ with minimal
magnetic charge $q_{m}=1$ the axion-photon coupling is
$\tilde{g}_{a\gamma\gamma}=3/(e_{0}^{2}f_{a})=27/(e^{2}f_{a})$, which is
plotted against axion mass $m_{a}$ and decay constant $f_{a}$ in fig. 2. This
result is consistent with the one we obtained using the Schwinger proper time
method in ref. [19]. In the latter article, we also discuss further
phenomenological implications, including axion-nucleon couplings and axion
dark matter for pre-inflationary PQ symmetry breaking.

Figure 1: Axion-photon coupling as a function of axion mass and decay constant
for KSVZ-like and DFSZ axion models together with the existing constraints on
the corresponding parameter space from experiments as well as from
astrophysical data. Astrophysical hints are also shown.

Figure 2: Same as fig. 2, but extended with the projected constraints from
future experiments (dashed lines) and with the blue line corresponding to the
model which accounts for the magnetic anomaly coefficients (for a particular
case of single new fermion $\psi$ with
$q_{m}=1\,,\;d\\!\left(C_{\psi}\right)=3\,$).

## Acknowlegments

A.R. acknowledges support and A.S. is funded by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s
Excellence Strategy – EXC 2121 Quantum Universe – 390833306.

## References

  * [1] R. Peccei and H.R. Quinn, _CP Conservation in the Presence of Instantons_ , _Phys. Rev. Lett._ 38 (1977) 1440.
  * [2] R. Peccei and H.R. Quinn, _Constraints Imposed by CP Conservation in the Presence of Instantons_ , _Phys. Rev. D_ 16 (1977) 1791.
  * [3] S. Weinberg, _A New Light Boson?_ , _Phys. Rev. Lett._ 40 (1978) 223.
  * [4] F. Wilczek, _Problem of Strong $P$ and $T$ Invariance in the Presence of Instantons_, _Phys. Rev. Lett._ 40 (1978) 279.
  * [5] J. Preskill, M.B. Wise and F. Wilczek, _Cosmology of the Invisible Axion_ , _Phys. Lett. B_ 120 (1983) 127.
  * [6] L. Abbott and P. Sikivie, _A Cosmological Bound on the Invisible Axion_ , _Phys. Lett. B_ 120 (1983) 133.
  * [7] M. Dine and W. Fischler, _The Not So Harmless Axion_ , _Phys. Lett. B_ 120 (1983) 137.
  * [8] J.E. Kim, _Weak Interaction Singlet and Strong CP Invariance_ , _Phys. Rev. Lett._ 43 (1979) 103.
  * [9] M.A. Shifman, A. Vainshtein and V.I. Zakharov, _Can Confinement Ensure Natural CP Invariance of Strong Interactions?_ , _Nucl. Phys. B_ 166 (1980) 493.
  * [10] M. Dine, W. Fischler and M. Srednicki, _A Simple Solution to the Strong CP Problem with a Harmless Axion_ , _Phys. Lett. B_ 104 (1981) 199.
  * [11] A. Zhitnitsky, _On Possible Suppression of the Axion Hadron Interactions. (In Russian)_ , _Sov. J. Nucl. Phys._ 31 (1980) 260.
  * [12] A. Ayala, I. Domínguez, M. Giannotti, A. Mirizzi and O. Straniero, _Revisiting the bound on axion-photon coupling from Globular Clusters_ , _Phys. Rev. Lett._ 113 (2014) 191302 [1406.6053].
  * [13] A. De Angelis, O. Mansutti, M. Persic and M. Roncadelli, _Photon propagation and the VHE gamma-ray spectra of blazars: how transparent is really the Universe?_ , _Mon. Not. Roy. Astron. Soc._ 394 (2009) L21 [0807.4246].
  * [14] D. Horns and M. Meyer, _Indications for a pair-production anomaly from the propagation of VHE gamma-rays_ , _JCAP_ 02 (2012) 033 [1201.4711].
  * [15] S. Troitsky, _The local-filament pattern in the anomalous transparency of the Universe for energetic gamma rays_ , _Eur. Phys. J. C_ 81 (2021) 264 [2004.08321].
  * [16] L. Di Luzio, F. Mescia and E. Nardi, _Window for preferred axion models_ , _Phys. Rev. D_ 96 (2017) 075003 [1705.05370].
  * [17] P.A.M. Dirac, _Quantised singularities in the electromagnetic field,_ , _Proc. Roy. Soc. Lond. A_ 133 (1931) 60.
  * [18] J. Polchinski, _Monopoles, duality, and string theory_ , _Int. J. Mod. Phys. A_ 19S1 (2004) 145 [hep-th/0304042].
  * [19] A.V. Sokolov and A. Ringwald, _Photophilic hadronic axion from heavy magnetic monopoles_ , _JHEP_ 06 (2021) 123 [2104.02574].
  * [20] D. Zwanziger, _Local-lagrangian quantum field theory of electric and magnetic charges_ , _Phys. Rev. D_ 3 (1971) 880.
  * [21] C. Csaki, Y. Shirman and J. Terning, _Anomaly Constraints on Monopoles and Dyons_ , _Phys. Rev. D_ 81 (2010) 125028 [1003.0448].