Quantum speedup in stoquastic adiabatic quantum computation
Keisuke Fujii







Department of Physics, Graduate School of Science, Kyoto University, Kitashirakawa-Oiwakecho, Sakyo-ku, Kyoto 606-8502, Japan
JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan




Quantum computation provides exponential speedup 
for solving certain mathematical problems against classical computers.
Motivated by current rapid experimental progress on 
quantum computing devices, various models of quantum computation 
have been investigated to show quantum computational supremacy.
At a commercial side, 
quantum annealing machine realizes the quantum Ising model 
with a transverse field and heuristically 
solves combinatorial optimization problems. 
The computational power of this machine 
is closely related to adiabatic quantum computation (AQC) 
with a restricted type of Hamiltonians, namely stoquastic Hamiltonians,
and has been thought to be relatively less powerful 
compared to universal quantum computers.
Little is known about computational quantum speedup 
nor advantage
in AQC with stoquastic Hamiltonians.
Here we characterize computational capability of 
AQC with stoquastic Hamiltonians, which we call stoqAQC.
We construct a concrete stoqAQC model,
whose lowest energy gap is lower bounded polynomially, and hence 
the final state can be obtained in polynomial time.
Then we show that it can simulate universal quantum computation 
if adaptive single-qubit measurements
in non-standard bases are allowed on the final state.
Even if the measurements are restricted to non-adaptive measurements
to respect the robustness of AQC,
the proposed model exhibits quantum computational supremacy;
classical simulation is impossible under complexity theoretical conjectures.
Moreover, it is found that such a stoqAQC model can simulate 
Shor's algorithm and solve the factoring problem in polynomial time.
We also propose 
how to overcome the measurement imperfections via quantum error correction
within the stoqAQC model and also
an experimentally feasible verification scheme 
to test whether or not stoqAQC is done faithfully.





Quantum speedup in stoquastic adiabatic quantum computation
    Keisuke Fujii
    December 30, 2023
===========================================================



§ INTRODUCTION

The Hamiltonians with
nonpositive off-diagonal elements 
in a standard basis
are called stoquastic Hamiltonians <cit.>.
Important quantum statistical models are 
included in this class. 
The quantum Ising model with a transverse field,
the antiferromagnetic Heisenberg model on bipartite graphs, 
and the Bose-Hubbard model with negative hoppings
are such examples.
For this class of models,
the ground state
has real and positive coefficients 
in the standard basis.
This allows 
a Monte-Carlo method on a classical computer,
called quantum Monte-Carlo,
to sample the ground state,
while efficient convergence
is not always guaranteed.

Another important aspect of stoquastic Hamiltonians 
is quantum annealing (QA) <cit.>, which 
is a heuristic algorithm to 
solve combinatorial optimization problems 
approximately by adiabatically (or even non-adiabatically) 
changing the parameters.
In the adiabatic case,
QA is included in an adiabatic quantum  computation (AQC) <cit.>,
which is known to be universal 
for quantum computation
when nonstoquastic Hamiltonians are employed <cit.>.
When it is restricted to stoquastic Hamiltonians,
its computational power has been speculated to be less powerful 
compared to universal quantum computation <cit.>.
From an experimental viewpoint, 
stoquastic Hamiltonians are relatively 
easy to be implemented.
This is why QA with the quantum Ising model
with a transverse field has been already 
implemented with a larger number of qubits 
on a superconducting system <cit.>,
while the quality of the qubits are relatively poor 
compared to the standard circuit-based approaches <cit.>.
Unfortunately, there has been little theoretical or experimental 
solid evidence of quantum speedup 
in AQC with stoquastic Hamiltonians <cit.>
except for the oracle problems <cit.>.

Computational complexity of stoquastic Hamiltonians 
has been investigated so far
in various aspects <cit.>.
Local Hamiltonian problems of stoquastic Hamiltonians
have been shown to be stoqMA-complete <cit.>.
Moreover, the local Hamiltonian problem of the quantum Ising model with 
a transverse field on degree-3 graphs is 
complete in the sense that 
it is equivalent modulo polynomial reductions 
to the local Hamiltonian problems of stoquastic Hamiltonians <cit.>.
StoqMA is the class of problems 
efficiently verifiable by reversible (unitary) classical computation, 
with an X-basis measurement,
whose input consists of 
a quantum state provided by a prover as the proof  
and ancilla qubits prepared in the Pauli X and Z bases.
While stoqMA is not so powerful as 
QMA <cit.>,


stoqMA includes MA and hence NP,
which are efficiently verifiable problems by 
probabilistic and deterministic classical computations,
respectively.
This implies that
computational complexity of the ground state energy of stoquastic 
Hamiltonians does not directly 
reflect computational power of 
AQC with stoquastic Hamiltonians;
the former is thought to be much harder than 
the latter.

The quench dynamics of stoquastic Hamiltonians 
is as powerful as universal quantum computation.
Quantum computational supremacy of quantum approximated 
optimization algorithm <cit.>, which is a digitalized version of 
QA, has been argued <cit.> by using the fact that 
Ising type commuting interactions on the eigenstates of 
the transverse field can simulate non-universal model,
so-called IQP <cit.> (instantaneous quantum polynomial time computation).
Even translation invariant quench dynamics on one-dimensional
quantum Ising model can simulate universal quantum computation <cit.>. 
Note that, quench dynamics of stoquastic Hamiltonians can 
generate negative (even complex) coefficients in the standard basis.
Moreover, quench dynamics does not inherit the robustness of 
AQC, i.e., protection as a ground state.
Regarding adiabatic dynamics,
the computational power of stoquastic Hamiltonians
has not yet fully understood.
Neither quantum computational supremacy nor the capability of 
universal quantum computation has been addressed so far.

Here we characterize computational capability of AQC 
with stoquastic Hamiltonians, which we call stoqAQC, 
and show that stoqAQC exhibits strong quantum speedup.
Based on AQC using the Feynman-Kitaev Hamiltonian <cit.>, 
we construct a stoqAQC model whose 
lowest energy gap is always lower bounded by 
the inverse of a polynomial function in the size of the system.
This guarantees that the final state can be faithfully 
obtained with a polynomial time.
Specifically, 
we consider both non-adaptive and adaptive single-qubit
measurements in the Pauli bases on the final state of the stoqAQC.
While this contains a non-standard basis,
it is not so difficult to perform non-standard basis
measurements, if the actual quantum machine works coherently.

In the case of the adaptive single-qubit measurements,
we can successfully show that 
stoqAQC can simulate universal quantum computation
only Pauli basis measurements.
However, such adaptive single-qubit measurements 
take time for the sequential measurements, and 
the final state would decohere during the measurements.
Therefore, non-adaptive measurements might 
be relevant to characterize an actual stoqAQC machine.
Even in the case of the non-adaptive measurements, 
we can show that stoqAQC can perform non-universal quantum computation,
which exhibits quantum speedup.
More precisely, 
stoqAQC can simulate
two types of 
non-universal models for quantum computational 
supremacy, IQP <cit.> and HC1Q (Hadamard-classical circuit with one-qubit) <cit.> models.
Moreover, we can show that stoqAQC 
can also simulate Simon's algorithm <cit.> 
and Shor's factorization algorithm efficiently <cit.>.
To this end, 
we slightly modify the phase estimation 
so that the phase is obtained with 
non-adaptive measurements without quantum Fourier transformation.
In this way, 
we find strong evidence that an ideal stoqAQC machine 
can provide plenty of quantum speedup.

Yet, this result does not mean that 
the state-of-the-art d-wave quantum annealer
designed to solve optimization problems
readily exhibits quantum speedup,
since it consists of relatively poor qubits and 
only employs the standard basis measurements.
In our construction, 
the final state is a highly entangled state
and the measurements are done in non-standard bases.
Therefore noise or imperfection in the system 
would affect the output crucially.
Moreover, the standard basis measurements only result in 
classical randomized computation in our construction.
Therefore, coherence in the final state is crucially important 
to gain quantum speedup in our construction,
though this would always be the case for any quantum computing device.

We further show that our construction is robust against 
measurement imperfections
by showing how to embed quantum error correction within the stoqAQC model.
We also argue how to verify whether or not the
proposed stoqAQC is faithfully done experimentally. 



§ STOQUASTIC ADIABATIC QUANTUM COMPUTATION

We adopt the following definition of AQC:
[AQC <cit.>]

A k-local adiabatic quantum computation is specified by two k-local Hamiltonians H_ initial and H_ final. 
The ground state of H_ initial is unique and is a product state. 
The output is a state that is ϵ-close in l_2-norm to the ground state of H_ final.
Let s(t):[0,t_f] ↦ [0,1] (the schedule) and 
let t_f be the smallest time such that the final state of an adiabatic evolution generated by H(s) = [1-s(t)]H_ initial+ H_ final 
for time t_f is ϵ-close in l_2-norm to the ground state of H_ final.
Then, arbitrary single-qubit measurements can be done 
adaptively or non-adaptively on the final state.

[StoqAQC <cit.>]

Stoquastic adiabatic quantum computation (stoqAQC) is the special case of AQC  restricted to k-local stoquastic Hamiltonians.

Following Ref. <cit.>,
we here use the term QA
when stoquastic Hamiltonians are employed 
to solve combinatorial optimization problems
either adiabatically or non-adiabatically.
Our construction 
employs a stoquastic version of 
AQC using the Feynman-Kitaev Hamiltonian <cit.>.
We consider a composite system 
ℋ_ work⊗ℋ_ clock
of the working system ℋ_ work = (ℂ^2)^⊗ (n+m)
and the clock system ℋ_ clock= ℂ^T+1,
where T= poly(n,m).
Later, the clock system is replaced by a (T+1)-qubit system 
by using the domain wall clock construction,
|t⟩ = |1_1...1_t 0_t+1...⟩ <cit.>.

The Hamiltonian is given by

    H(s)= (1-s) H_ initial + s H _ final,

where

    H_ initial   =    
    H_ in
    + (I_c - |0⟩⟨ 0| _c ),
    
    
    H_ final   =    H_ in+ ∑ _t=1^T1/2 [ 
    |t⟩⟨ t|_c + |t-1⟩⟨ t-1 |_c 
    
          
    - (U_t  |t⟩⟨ t-1| _c +  h.c. ) ],

with the energy penalty term for the initial state of the working system,

    H_ in=∑ _i=1^n |1⟩⟨ 1|_i ⊗ |0⟩⟨ 0 | _c 
    +∑_j=n+1^m+n |-⟩⟨ - |_j  ⊗ |0⟩⟨ 0 | _c ,

imposing the initial state |0⟩^⊗ n |+⟩ ^⊗ m .
The unitary operator U_t 
acting on the working system
consists only of Toffoli, CNOT, and X.
This guarantees that H(s) is stoquastic for 0≤ s ≤ 1
in the standard basis 

    { |0⟩ , |1⟩}^⊗ (n+m)⊗{ |t⟩_c }_t=0^T .


The parameter s is adiabatically changed from s=0 to s=1.
The ground state of the initial Hamiltonian 
H_ initial is 

    |η _0⟩ =  |0⟩ ^⊗ n |+⟩ ^⊗ m |0⟩ _c.

The ground state of the final Hamiltonian 
H_ final is 

    |Ψ⟩ = 1/√(T+1)∑ _t=0^T | η _t⟩,

where 

    |η _t ⟩ =  U_t ⋯ U_1 | 0⟩ ^⊗ n |+⟩ ^⊗ m |t⟩_c



































Furthermore, 
regarding the minimum energy gap Δ 
between the ground and first excited state of H(s) (0≤ s ≤ 1),
we can make
the same argument as Ref. <cit.>
for AQC with general Hamiltonians.
This guarantees Δ is 
lower bounded by O(1/T^2).
By virtue of the adiabatic theorem,
there exist a certain constant c(k)
for any constant k such that
if the computation time is sufficiently long

    t ≥ c(k) H_ final - H_ initial^1+1/k/ϵ ^1/kΔ^2+1/k,
 
then the final state |Ψ _ ad⟩ 
is ϵ-close to the exact ground state |Ψ⟩
in l_2-norm <cit.>.

On the current QA machine,
measurements are done only in the standard computational basis,
in which the Hamiltonian is stoquastic.
Here we slightly relax this condition,
and assume that arbitrary single-qubit measurements
can be done on the final state either adaptively or non-adaptively.
(Note that the measurement basis is not 
restricted in Defs. <ref> and  <ref>
as is also stated in Ref. <cit.>.)
Suppose the clock state is measured, and 
the state |T⟩ is obtained,
which occurs with a high probability ≥ 1/ poly(n,m).
It is known that this probability can be further amplified 
to a constant value <cit.>, say 1/2, 
by inserting the identity gates (T-1) times
using the clock system { | t ⟩_c}_t=0^2T-1.
The ground state is given by 

    |Ψ⟩ 
    = 1/√(2T)∑ _t=0^2T-1 | η _t ⟩,

where U_t = I for T+1 ≤ t ≤ 2T-1.
Any clock states in the rage T ≤ t ≤ 2T-1 allow
us the desired computation.

Under the condition of obtaining 
a successful clock state,
the computation, which we can perform on the final state,
is specified to be

    U_T ⋯ U_1 (I^⊗ n⊗ H^⊗ m)|0⟩ ^⊗ (n+m)

followed by arbitrary 
non-adaptive or adaptive single-qubit measurements
as shown in Fig. <ref> (a).
If the measurements in Fig. <ref> are restricted to the computational basis,
it corresponds to classical randomized computation.
When measurements on xy-plane are additionally available,
it belongs to Fourier hierarchy (FH) of the second level, FH_2 <cit.>.
If the initial states and measurements are restricted into 
|0⟩ ^⊗ n |+⟩ and 
X and Z basis measurements on them
, the circuit in Fig. <ref>
corresponds to HC1Q model <cit.>.
Then, for arbitrary single-qubit measurements,
it is included in FH_3. 




Since U_T ⋯ U_1 contains CNOT gates,
this readily tells us that 
an arbitrary CSS (Calderbank-Shor-Steane) state <cit.>
can be prepared from the final state via 
the measurement on the clock.
More generally, we have

An arbitrary state that is generated 
by a polynomial number of X, CNOT, and Toffoli gates
from |0⟩ ^⊗ n |+⟩ ^⊗ m
can be prepared efficiently by stoqAQC.

If we are allowed to perform arbitrary single-qubit measurements,
we can show that universality with adaptive measurements 
using measurement-based quantum computation <cit.>
and quantum computational supremacy with non-adaptive measurements <cit.>
as follows.



§ UNIVERSALITY WITH ADAPTIVE MEASUREMENTS




Let us consider a more elaborate and concrete 
model with a 6-local Hamiltonian.
Let us consider a union jack lattice
as shown in Fig. <ref>,
where the qubits in the working and clock systems are located on 
the vertices (white and red circles) and face centers (blue circles)
of the triangles, respectively.
The qubits on the working system are prepared 
|0⟩ and |+⟩ on the white and red colored qubits,
respectively.
By introducing the domain wall clock
|t⟩ = |1_1 ⋯ 1_t 0_t+1⋯⟩ ^c
localized on the triangle centers <cit.>,
the Hamiltonian is given by

    H̃_ initial   =    
     H_ initial + H_ clock
    H̃_ final   =   
    H_ final + H_ clock

with the energy penalty terms for the illegal clock states,

    H_ clock = ∑ _i=1^T-1 |01⟩⟨ 01|^c_i,i+1.

The superscript c denotes the clock system.
Moreover, following replacements in H_ initial and H_ final 
are also performed: 

    |0 ⟩⟨ 0|_c 
       →    |0⟩⟨ 0|^c_1
    
    I_c -|0 ⟩⟨ 0|_c     →    |1⟩⟨ 1|^c_1
    
    |t⟩⟨ t-1|_c    →    |110⟩⟨ 100 |^c_t-1,t,t+1,
    
    
    |t-1⟩⟨ t-1 |_c    →    |100 ⟩⟨ 100| _t-1,t,t+1^c,
    
    
    |t⟩⟨ t |_c    →    |110 ⟩⟨ 110| _t-1,t,t+1^c,

where |1⟩ _t-1 and |0⟩ _t+1 
are not required for the initial t=0 and final t=T clock states, respectively.
Note that if a high energy penalty term for illegal clock states 
is introduced, the clock operator can be described by fewer body operators <cit.>. However, the Hamiltonian can be finally
mapped into 2-local one perturbatively by using mediator qubits <cit.>,
and hence we employ the original 5-local construction in Refs. <cit.>.
U_t in H_ final 
corresponds to the Toffoli gate
acting





on three qubits on the triangle corresponding 
to the t-th clock qubit,
where white and red qubits act as the controls and target,
respectively, 
as shown in Fig. <ref>.
Under the condition of projecting the clock state
to |11...1⟩^c on the final state,
the union jack state is obtained.
The union jack state is known to be a universal resource 
for measurement-based quantum computation with the Pauli basis measurements <cit.>. 
Therefore, stoqAQC with adaptive Pauli measurements 
is universal. 

6-local StoqAQC with adaptive Pauli basis measurements can 
simulate universal quantum computation efficiently.

The 6-local interactions can be reduced to 2-local 
perturbatively by using the mediator qubits <cit.>.



§ QUANTUM COMPUTATIONAL SUPREMACY WITH NON-ADAPTIVE MEASUREMENTS

The advantage of AQC 
would its protection against decoherence 
by the Hamiltonian.
However, the adaptive measurements 
considered above would deteriorate this good property,
since the resource state might decohere during the 
measurements. (Later, we will also see
how to make stoqAQC robust against the measurement imperfections.) 
If we consider a robust physical 
implementation, non-adaptive measurements on the 
final state would be preferred.
Even in such a case, 
we can show strong evidence of quantum speedup of stoqAQC
as follows. 

Measurement-based quantum computation on the union jack lattice and 
HC1Q are both known to be universal under postselection <cit.>.
Therefore, non-adaptive measurements on the exact ground state |Ψ⟩
are as powerful as postBQP <cit.> under postseleciton.
This indicates that 
classical (non-adaptive) sampling in the Pauli bases
with a constant l_1 additive error
is impossible 
under complexity theoretical conjectures <cit.>:

Based on anti-concentration conjecture 
and average v.s. worst case conjecture
of HC1Q or IQP with the union jack state, 
efficient classical simulation of 
6-local stoqAQC with non-adaptive Pauli basis measurements 
with a small constant l_1 additive error 
implies the collapse of polynomial hierarchy to the third level.

Again, the 6-local interactions can be reduced perturbatively to 2-local <cit.>.

Proof. 
Below we will first show that 
the sampling on the polynomial-time stoqAQC 
is sufficiently close to the output of the ideal circuit 
shown in Fig. <ref> (a) in l_1-norm.
Then, a classical sampling of such stoqAQC
with a constant l_1 additive error implies 
a classical simulation of the output of the ideal circuit 
with a constant l_1 additive error.

Due to the adiabatic theorem, 
the final state |Ψ _ ad⟩
satisfying 

    |Ψ _ ad⟩  - | Ψ⟩_2 <ϵ

can be obtained in polynomial time in the size of computation.
From this we have 

    |⟨Ψ_ ad | Ψ⟩ |> 1- ϵ /2 ≡ f.

By using the relation between 
fidelity and trace distance,
we have

    1/2ρ  -  ρ̃_1 = √(1- f^2 )≡δ ',

where ρ≡ |Ψ⟩⟨Ψ | and ρ̃≡
|Ψ _ ad⟩⟨Ψ _ ad | are both pure states.
Let P(x)=W^†|x⟩⟨ x|W be
projectors corresponding to the measurement outcome x∈{ 0,1}^n+m 
on the working system
with W being a product of single-qubit unitary operators for the basis change,
and P_ clock be the projector corresponding to the successful clock states.
The ideal probability distribution of 
the circuit in Fig. <ref> (a)
is given by 

    p(x) =  Tr[P(x)P_ clockρ]/ p_ clock,

where p_ clock =  Tr[P_ clockρ ].
Similarly, p̃(x) and p̃_ clock
are defined for the final state ρ̃ 
of the adiabatic operation.
Since for any POVM (positive operator valued measure) operators { M_y },
we have 

    q(y) - q̃ (y) _1 
     ≤ρ - ρ̃_1

where q(y) =  Tr[M_y ρ] and q̃(y) =  Tr[M_y ρ̃].
Then we have 

    ∑_x | p(x)p_ clock - p̃(x) p̃_ clock|
    ≤  2δ',

and 

    |p_ clock - p̃_ clock| ≤ 2δ ' .

On the other hand,

    ∑_x | p(x)p_ clock - p̃(x) p̃_ clock|
    
       ≥   ∑ _x| [p(x) - p̃(x)]| p_ clock 
    - |p_ clock- p̃_ clock|
    
       ≥   ∑ _x |p(x) - p̃(x)] |  p_ clock
    - 2δ '.

By combining Eqs. (<ref>) and (<ref>),

    p(x) - p̃(x)_1 ≤ 4 δ' /p_ clock≡δ”.

Therefore,
to achieve a polynomially small 
l_1 additive error δ” = 1/ poly(n,m),
we need δ'< δ” p_ clock/4.
This means that the final state of an accuracy 

    ϵ < 2 ( 1- √(1- (δ”p_ clock/4)^2))

in l_2-norm 
is enough.
This and Eq. (<ref>) guarantees that 
the computation time of the stoqAQC is 
still polynomial time in (n,m).

Suppose classical efficient sampling of
stoqAQC with a l_1 additive error η is possible,
a similar argument tells us 
the conditional probability distribution 
p_ samp(x) on the working system satisfies 

    p_ samp(x) - p̃(x)_1    <    2η /p̃_ clock
       <     2η /(p_ clock - 2 δ' )

where we assume 2δ' < p_ clock.
Note that 2 δ ' = δ” p_ clock /2 is small enough.
Moreover, p_ clock can be a constant,
and we chose p_ clock = 1/2.
Then, the l_1 additive error between 
conditional probability distributions 
from classical sampling p_ samp(x) and the ideal one p(x)
is bounded by a constant value

    p_ samp(x) - p(x)_1
       <    p_ samp(x) - p̃(x)_1 + p̃(x) - p(x)_1
    
       <     4η /(1 - 4 δ' )  + δ”.

Both δ ' and δ”
can be made small by improving the accuracy ϵ of the 
stoqAQC as seen in Eq.(<ref>), 
which is the target of the classical simulation.
Therefore, 
classical conditional sampling p_ samp(x)
is constantly close to p(x) with l_1 additive error.
The probability distribution p(x) 
contains IQP on the union jack lattice <cit.> and HC1Q model <cit.>,
both of which are shown to be postBQP-complete under postselection.
Therefore, 
by assuming that the anti-concentration and average v.s. worst case conjectures
are correct in these models,
a classical efficient sampling of stoqAQC 
with a small constant l_1 additive error 
leads to the collapse of the polynomial hierarchy to the third level.
▪

Here we should note that 
while a decision problem on stoqAQC 
with a single-qubit X-basis measurement on the working system
and computational basis measurements on the clock system
corresponds to stoqMA 
with a trivial proof |0⟩ ^⊗ n |+⟩ ^⊗ m,
and hence is upper bounded by postBPP <cit.>.
Although this has been thought to be a partial evidence of 
the weakness of computational power of stoqAQC,
the sampling problem on stoqAQC with non-standard bases 
can be much harder leading to postBQP under postselection and 
exhibits quantum computation supremacy as seen above.




§ QUANTUM SPEEDUP WITH NON-ADAPTIVE MEASUREMENTS




Next we show that 
stoqAQC with non-adaptive single-qubit measurements 
can solve the factoring problem by simulating 
Shor's algorithm.
Since any classical reversible (unitary) computation can be 
done on the circuit shown in Fig. <ref>, 
the modular exponentiation can also be implemented.
We employ the Kitaev's original 
phase estimation <cit.>,
where adaptive single-qubit measurements 
are performed without the 
inverse quantum Fourier transformation.
Furthermore, 
in order to avoid the adaptive measurements, 
we introduce a non-adaptive iterative phase estimation 
as shown in Fig. <ref>.

Let N and x be an integer to be factorized and 
its coprime respectively, 
and define U_x = ∑ _y |xy  (mod N)⟩⟨ y|,
where y=1,...,N.
Let r be the order, the minimum integer satisfying x^r ≡ 1
modulo N.
An eigenstate of U_x with a label s (0≤ s ≤ r-1) is given by

    |u_s⟩ = 1/√(r)∑ _k=0^r-1 e^- 2 π i (s/r)k |x^k (mod N)⟩.
 
The eigenvalue e^2 π i (s/r) is 
written in terms of the binary representation 
by e^(2 π i )0.j^(s)_1 ... j^(s)_l (j^(s)_k ∈{ 0,1}).
As usual, the phase estimation is done on the state

    |1̅⟩ = 1/√(r)∑ _s=0^r-1 |u_s⟩,

where the notation |1̅⟩
is employed to avoid the confusion with the basis state |1⟩ of a qubit.

As shown in Fig. <ref>,
we perform 2R iterative phase estimation 
of U^2^k
with non-adaptive measurements for each k=0,...,l-1.
The first and second R iterations are measured 
in the X and Y basis non-adaptively.
The state before the measurement is written by 


    1/√(r)∑ _s=0^r-1(|0⟩ + e^(2π i) 0.j^(s)_1 ... j^(s)_l |1⟩/√(2))^⊗ 2R⋯(|0⟩ + e^(2π i) 0.j^(s)_k ... j^(s)_l |1⟩/√(2))^⊗ 2R⋯(|0⟩ + e^(2π i) 0. j^(s)_l |1⟩/√(2))^⊗ 2R | u_s⟩.


While the measurements are done non-adaptively,
we below employ an inductive argument for explanation.
Let us first consider the measurements on 

    (|0⟩ + e^(2π i) 0. j^(s)_l |1⟩/√(2))^⊗ 2R.

Since j^(s)_l is either 0 or 1,
we can easily determine j^(s)_l 
from the R measurement outcomes in each X and Y bases.
The R samples are enough to decide j^(s)_l=0,1 with an 
exponential accuracy by using Hoeffding's inequality,
since expectation values of the angle
θ _l ≡arctan (⟨ Y⟩ / ⟨ X ⟩) 
is constantly separated by π for j^(s)_l=0 or =1.
We can think this process just as a tomography of

    |0⟩ + e^(2π i) 0. j^(s)_l  |1⟩/√(2)

using 2R samples on the xy-plane of the Bloch sphere.

Next, suppose j^(s)_k-1,...,j^(s)_l are all determined already.
Then we perform the sampling on 

    (|0⟩ + e^(2π i) 0.j^(s)_k ... j^(s)_l |1⟩/√(2))^⊗ 2R .

Since j^(s)_k-1,...,j^(s)_l are determined already,
the expectation value of the angle

    θ _k = arctan (⟨ Y ⟩ / ⟨ X ⟩ ),

evaluated by the state

    (|0⟩ + e^(2π i) 0.j^(s)_k ... j^(s)_l |1⟩/√(2)),




is again constantly separated by π for j^(s)_k=0,1 cases.
Therefore, from 2R measurement outcomes,
we can determine j^(s)_k with an exponential accuracy 
in the number of samples R by using Hoeffding inequality 
for ⟨ X⟩ and ⟨ Y ⟩.
Inductively, all binary bits, j_1^(s),...,j_l^(s), are determined.
Again, we should note that the measurements are non-adaptive
and hence can be done simultaneously.
From the obtained phase,
the order r is obtained by using the continued fraction as usual.
Then, a non-trivial factor of N is found with a high probability
against a random choice of x.

The circuit shown in Fig. <ref> 
consists only of X, CNOT, and Toffoli
acting on the initial |0⟩s and |+⟩s.
Therefore, including the measurements on the clock,
we conclude that 
stoqAQC with non-adaptive single-qubit measurements 
can solve the factoring problem in polynomial time 
by simulating Shor's algorithm.
If measurement bases are restricted to X and Z,
still stoqAQC with non-adaptive measurements 
can solve Simon's problem <cit.>.
Since swap operations can be constructed from CNOT gates,
the stoquastic Hamiltonian can be reduced to spatially two-local one on 
a two-dimensional lattice by localizing the domain wall clock <cit.>
and applying perturbative approach with the mediator qubits <cit.>.



§ VERIFICATION AND MEASUREMENT ERROR TOLERANCE

Our construction
based on the Feynman-Kitaev construction
naturally provides a verification 
protocol of whether or not the final state of stoqAQC is 
faithfully generated.
Several verification protocols 
with single-qubit measurements 
have been proposed so far 
based on the Kitaev-Feynman construction <cit.>
and can be readily applied to the present stoqAQC Hamiltonians.

The history state |Ψ⟩
is the unique ground state of the final Hamiltonian H_ final
and satisfies 

    E_g= ⟨Ψ | H_ final |Ψ⟩ = 0.

Any pure state can be 
expanded by the energy eigenstates { |E_i ⟩}
with eigenvalue {E_i}, respectively:

    |ψ⟩ = α _0 |E_0 ⟩ + ∑ _i=1^(T+1)2^(n+m)-1α _i | E_i ⟩,

where |E_0⟩ = |Ψ⟩ and E_0 =0.
The energy expectation value becomes 

    ∑ _i=0^(T+1)2^(n+m)-1  |α _i |^2 E_i > (1-|α_0|^2) Δ .

(Its extension to the mixed states is straightforward.)
Therefore, by measuring the energy expectation value E_ exp 
of the final state
within an additive error 
and by checking whether or not 

    E_ exp < ϵ_ verΔ

is satisfied with polynomially small ϵ_ ver= 1/ poly(n,m),
we can verify that the overlap between 
the experimentally obtained state |ψ⟩
and the ideal final state |Ψ⟩ is 
sufficiently large |α _0|^2 > 1-ϵ_ ver.
Note that the fidelity is given by 
|⟨ψ | Ψ⟩|=|α _0|.
The measurement of the energy can be 
done by polynomially repetitive single-qubit measurements on the final state
as done in variational quantum eigensolver <cit.>.
A more elaborated verification scheme as done in Ref. <cit.>
can also be employed.

Furthermore, 
as mentioned before,
if the measurement basis is restricted 
to the xy-plane or the Z basis,
stoqAQC belongs to FH_2.
Therefore, the output x 
can be verified efficiently 
by using the fact that a decision problem in FH_2 is in MA <cit.>.

Finally, we consider the robustness of the proposed 
stoqAQC model against a measurement imperfection.
Even if AQC is executed ideally,
the final measurements, especially
done in the non-standard Pauli bases, would causes 
an imperfect readout.
Fortunately,
the measurements are done all in the Pauli bases.
The encoding circuit of CSS codes, such as 
the Steane 7-qubit code <cit.>,
consists only of CNOT gates acting on 
|0⟩s and |+⟩s.
Therefore,
by adding the further working and clock qubits,
we can encode each qubit in the final state into 
a self-dual CSS code as shown in Fig. <ref> (b).
For the self-dual CSS code, like the Steane 7-qubit code,
all logical Pauli basis measurements are done 
transversally by single-qubit Pauli basis measurements.
Therefore quantum speedup of stoqAQC is at least robust against 
the measurement imperfections in the non-standard basis.
While we employ non-fault-tolerant encoding circuit of the CSS code,
the encoded state is prepared as a ground state in AQC,
and hence it would be interesting to see whether or not 
this type of encoding improves the accuracy of computation 
against imperfections during adiabatic operations or 
finite temperature effects.



§ DISCUSSION

Here we characterized computational power of 
stoqAQC with adaptive or non-adaptive 
single-qubit measurements in the non-standard bases.
While our stoqAQC model employs 
the 6-local stoquastic Hamiltonian,
it is straightforward to reduce it to 
a 2-local stoquastic Hamiltonian as shown in Ref. <cit.>.
While the mediator qubits are added,
the original Hamiltonian is simulated perturbatively 
on the original system. 
Hence single-qubit measurements are enough for our purpose.
However, in the case of the reduction from the 2-local stoquastic Hamiltonian 
to a transverse Ising model (on degree-3 graphs) shown in Ref. <cit.>,
each qubit is simulated by dual rail bosons, a hard-core dimer
and an Ising spin (chain). 
This modifies the single-qubit measurements 
in the original model
to non-local measurements on the mapped models.
Therefore, 
the computational power of stoqAQC with 
single-qubit measurements in non-standard bases
is open for the transverse Ising models.

Our result implies that 
non-stoquasticity is not necessarily required 
to get quantum speedup in an AQC machine.
Instead, quantum coherence of the final state and 
non-standard basis measurements are key ingredients.
Since the lowest energy gap closes inverse polynomially, 
a finite temperature effect would be crucial.
A fault-tolerance theory would be further required to 
achieve scalability.
An arbitrary CSS state can be prepared in an adiabatic way,
which would be interesting itself as 
a robust entangled state generation scheme
using only two-body stoquastic interactions.
Moreover, 
our construction can also be viewed as 
measurement-based quantum computation 
on a ground state of two-body Hamiltonians
 <cit.>.
In such a context, 
thermal equilibrium states are also known 
as universal resources <cit.>.
These constructions might be helpful 
in a construction of a fault-tolerant theory
of stoqAQC at finite temperature.
In addition, the embedding of the CSS state would be also 
useful for this purpose.

Finally, it would be interesting to see
whether or not quantum Monte-Carlo or other classical methods 
relevant for stoquastic Hamiltonians can cope with
the final basis change at the measurements.
It would be natural to conjecture that 
stoqAQC with a polynomially bounded lowest energy gap
can be classified into
three classes by the types of the measurements:
(i) classically simulatable with standard basis measurements, 
(ii) non-universal but quantum computational supremacy with non-adaptive non-standard basis measurements,
and (iii) universal with adaptive non-standard measurements.

In the most models exhibiting quantum computational supremacy <cit.>,
the sampled output itself is not so useful, 
except for the one-clean qubit model <cit.>
and HC1Q <cit.>.
The present result has pushed 
stoqAQC to one of the most powerful intermediate model of quantum computation,
which exhibits quantum computational supremacy and 
can solve a meaningful problem, such as the factoring problem.


The author would like to thank
Keiji Matsumoto, Tomoyuki Morimae, Yuki Takeuchi, and Shuhei Tamate
for valuable discussions and comments on the draft.
This work is supported by KAKENHI No. 16H02211, JST PRESTO JPMJPR1668, JST ERATO JPM- JER1601, and JST CREST JPMJCR1673.


apsrev4-1



