Impact of the malicious input data modification on the efficiency of quantum spatial search
Adam Glos Jarosław Adam Miszczak



1,2]Adam Glosaglos@iitis.pl
1]Jarosław Adam Miszczak
[1]Institute of Theoretical and Applied Informatics, Polish Academy of
	Sciences, Bałtycka 5, 44-100 Gliwice, Poland
[2]Institute of Informatics, Silesian University of Technology,
	Akademicka 16, 44-100 Gliwice, Poland








Impact of the malicious input data modification on the efficiency of 
quantum spatial search
    [
    
============================================================================================


		In this paper we demonstrate that the efficiency of quantum spatial search can
be significantly altered by malicious manipulation of the input data in the
client-server model. We achieve this by exploiting exceptional configuration
effect on Szegedy spatial search and proposing a framework suitable for
analysing efficiency of attacks on quantum search algorithms. We provide the
analysis of proposed attacks for different models of random graphs. The
obtained results demonstrate that quantum algorithms in general are not secure
against input data alteration.
	
	



§ INTRODUCTION
 




  
Motivation 
	
While the intensive research effort invested in the area of quantum computing is
fully justified by groundbreaking theoretical
developments <cit.>, year
by year scientists have discovered new limitations of quantum computing
devices <cit.>. Quantum algorithms have been proved to be
susceptible to noise, which may falsify the results of the computation. This
fact motivated the development of the theory of quantum error-correcting codes.
Unitary operation decomposition provides numerous problems including
applications to hardware with fixed topology <cit.>. These
aspects started to play critical role after first commercial quantum computing
systems became available. Furthermore, hardware attacks, based on the security
holes of conventional electronics, have been discovered for quantum
cryptographic protocols <cit.>. The issues mentioned above
demonstrated that the theoretical security confirmed by the laws of physics in
the ideal environment could be deceptive in the real-world applications. For the
users it is important to be aware that quantum algorithms are inefficient for
some types of input data. One of such examples is quantum spatial search, which
is inefficient on 2D grid <cit.>. This demonstrates that the
quantum algorithms are not only unsuitable for some types of problems, but, even
for generally optimal quantum algorithms <cit.>, it is
possible to construct input data rendering them slow.
	
These examples show that, while quantum algorithms may be a milestone
in computational theory, their practical implementation and security still need 
to be carefully
checked. From the computational complexity point of view, it remains unknown whether 
the existing quantum algorithms can provide the speed-up promised by the
theoretical results, especially when applied to large datasets. 
On the other hand, the ability to describe the types of data which render quantum algorithms
ineffective can be used to develop post-quantum protocols.

Furthermore, as the remote utilization of quantum computational resources plays 
vital role for the development of quantum technologies, one should consider 
various aspects of the functioning of quantum devices accessed remotely. 
Currently, quantum transmission protocols used for Universal Blind Quantum 
Computation <cit.> can be used for transferring quantum 
data unknown to the server. Such protocols provide also correctness of the data and 
authentication of the transmission. However, they cannot be used for 
preventing the situation when maliciously prepared data are provided and result 
in the undesired behavior of quantum machine. This might lead, for example, 
resulting in denial of service effect. The analysis of the impact that the 
malformed data can have on the quantum computing infrastructure is still 
missing and this aspect of using quantum computers in the cloud deserves more 
attention.





  
Contribution






In this paper study how the input data can influence the efficiency of quantum 
algorithms based on quantum spatial search. We demonstrate that the efficiency 
of quantum algorithms can be significantly diminished by manipulation of the 
input data. For the purpose of this paper we consider the following scenario. 
We have two parties, Alice and Bob. Alice prepares input data and sends them to 
Bob, who has for his disposal quantum computational resources. Alice requests 
from 
Bob some kind of processing eg. sorting a list or finding  its maximum. This 
situation naturally occurs in cloud computing scenario. If the input data are 
altered by a third party, Eve, then the computational process executed by Bob 
may require more resources then initially assumed. In this situation Bob might 
not be able to handle queries from other users. However, the client-server 
scenario we consider here can also include the possibility that Alice is 
responsible for sending data which are already malformed. This might result 
either from the purposeful acting of Alice or from the fact that the data 
contain instances of problems which are hard for quantum computers to handle.

As an example one can consider a sorting via classical algorithm QuickSort. The
algorithm achieves average-case performance O(nlog (n)), for number of
elements n. However, for simple fixed pivot choice, one can provide malicious
input data, which increase computation time up to O(n^2). If no security is
considered, choosing such data may considerably increase the computational
resources required for running the algorithm. If the computer processes such
data, this may result in denial-of-service. Fortunately, there are known
solutions to this problem, for example, choosing pivot randomly.
	
Similar problems arise in the quantum spatial search, based on different models
of quantum walks. For the continuous-time quantum walk, the algorithm works very
well and securely on many graphs
<cit.>, achieving
efficiency O(√(n)), for the graph order n. However, there are known
examples, such as a two-dimensional grid, for which the algorithm reaches linear
complexity only <cit.>. While the grid graph can be searched
much faster for the discrete coined quantum walk, it is known that specific
subgraphs of the searched graphs can form so-called exceptional
	configurations <cit.> which strongly reduce the
efficiency.

In this paper we consider the formation of exceptional configurations as a
method of attacking quantum spatial search. We propose a framework enabling the
analysis of the attack efficiency based on the expected runtime of the
algorithm. We utilize this framework for selected families of random graphs. We
take into account different resources available for the attacker. We also
discuss the connection between our results and the security protocols used for
Universal Blind Quantum Computation.





§ PRELIMINARIES



Let =(,) be an undirected graph and let ⊂
V be a set of searched vertices. A quantum spatial search algorithm is a
quantum walk, which after t steps finds any marked v∈ with
probability p. While the classical spatial search is known to have time complexity
Ω(n), it is possible to achieve Θ(√(n)) for quantum
algorithms <cit.>. The complexity may depend on a chosen graph <cit.> or a chosen set  <cit.>. Throughout this paper we assume that the complexity of the quantum spatial search grows as Θ(n^α) for some α>0 which is commonly observed for many types of graphs.

For discrete coined quantum walk (DCQW), the search problem with
multiple marked vertices can be a hard
task for some combinations of marked vertices, known as exceptional configurations <cit.>. The existence of an exceptional configuration is demonstrated in two steps. First, the existence of a special stationary state needs to be shown. Second, a bound on the probability needs to be determined, based on the stationary state. Recently, the class of connected subgraphs having the stationary state has been described, which solves the first step.
[<cit.>]
	Let  be an arbitrary graph. Let H be its induced connected subgraph. H contains a stationary state, if
	
		
  * it is not bipartite, or
		
  * it is (_^1,_^2)-bipartite satisfying 
			
    ∑_v∈_^1_(v)=∑_v∈_^2_(v),

		where _ is the degree in graph . 
	

The exceptional configuration of order 2 (2EC) is a path of length 2, such that
the degrees of vertices in the original graph G are equal. The exceptional
configuration of order 3 (3EC) is a triangle graph, or a path of length 3, such
that the degree of the middle vertex equals the sum of the degrees of the end
vertices in the original graph G. Wong has shown the equivalence between
coined and Szegedy model (SzQW) <cit.>,
which is a general quantum walk definable on an arbitrary directed graph. We are
going to focus on the latter, as it is more suitable for numerical analysis.




§ DESCRIPTION OF THE ATTACK




Let us assume that Alice sends to Bob a description of the oracle, for example
in the form of the quantum circuit. Bob executes Szegedy quantum search based on
the obtained oracle. As a result Bob sends to Alice a marked vertex, found by
the algorithm. In this situation Bob expects to take advantage of the
capabilities of quantum computer and obtain the result within time
Θ(t^α).

Let us now assume that Eve has her own quantum resources and intercepts the
description of the oracle send by Alice. She executes the algorithm and finds
the vertex in time Θ(t^α). Then she creates a description of new
oracle, in which additional vertices is marked, and sends it to Bob. If marked
vertices form an exceptional configuration, then Bob will need Θ(t^β)
time to execute the algorithm, with β>α. One should note that
modification of input data send by Eve cannot be corrected by using the error
correction code, as the modification are made on a logical level.

Bob may detect that the oracle was altered if the algorithm consumes more
resources that it was initially assumed. Additionally, we assume that Bob knows
that the oracle has been modified by marking the additional vertices. This is
the worst possible scenario from Eve's perspective. In this situation he can
modify the hyperparameters of his algorithm to limit the adverse effect. The
simplest strategy is to change the measurement time. By this he may reduce the
execution time to Θ (t^β), with
β<β.



 §.§ Framework for quantifying the efficiency of attacks


For the purpose of quantifying the efficiency of attacking methods, we introduce the
formal description of the family of quantum spatial search algorithms.


	Quantum Spatial Search  is a tuple 
	(,t;,,θ), where  is a quantum algorithm 
	searching for any vertex v∈ in time t, running on graph G,
	and parametrized by the set of parameters θ.

By p() we denote the success probability of . Note that we do not
define θ precisely, as it depends on the chosen algorithm . For
example, for coined quantum walk =DCQW, the parametrization
consists of the set of coin operators. For =SzQW, the parametrization
is the chosen stochastic operation P.

In order to compare different quantum spatial search algorithms we propose the following measure of efficiency.

Expected runtime _ of quantum spatial search
=(,t;,,θ) is defined as
	
    _t/p().


The expected runtime is an expectation of number of steps after which we get the
result using Bernoulli process. Such approach has been used in
<cit.>, where the complexity was analysed.


Using the formalised description of quantum spatial search algorithms, we can
introduce the concept of attack on an algorithm as follows.


	Attack on  is a function h such that 
	
    h(,t;,,θ) = (,t;',',θ').



It should be stressed that the attack cannot change the evolution model and
measure time of . Still we will consider the function altering only
some of the elements of . For example, the attacks restricted to graph structure
imply that =' and θ=θ'. 

If we allow  element to be changed, then we will say the element is
hackable. Otherwise, it is not hackable. Note that by definition 
and t are not hackable.

To quantify the efficiency of the attacks we introduce attack efficiency
as follows.


Attack efficiency _h, on  is defined as

    _h, 1-_/_h().


We are interested in such functions h that _h,≥ 0. Furthermore,
since t is common for both  and h() we have 

    _h,=1-p(h())/p().


Let us consider the following scenario. The user is trying to start an algorithm
, but the attacker has changed it into '. If the user is aware of the attack and its nature, he can alter the
measurement time t in order to minimize the expected runtime. To describe
this situation we introduce strong attack efficiency.

 
Suppose we have = (,t;,,θ) and h:↦
(,t;',',θ'). Strong attack efficiency
_h, is defined as

    _h,
    1-_(,t;,,θ)/min_τ≥
    		0_(,τ;',',θ').


This definition captures the best possible defence against
the attack.

All of the above definitions were restricted to the fixed spatial search
algorithm. Since our aim is to analyse the efficiency of attacks on more
general graph classes, we extend the previously defined terms.

Let Q be a set of quantum spatial searches and h be an attack on Q. Then
maximal attack efficiency on Q, _h,Q, is defined as

    _h,Qmax_∈ Q_h,.

Similarly, maximal strong attack efficiency on Q, _h,Q, is defined as

    _h,Qmax_∈ Q_h,.


The above definition captures the pessimistic level of robustness against the attack.
Similarly, we can define the mean and minimal efficiencies. In practice, we
would like to find the dependence between the efficiency and the order of the
graph. 



Instead of providing deterministic Q_n, we will focus on Q_n defined by
random graph models _n. 

Let _n be a random graph model, and let for
arbitrary  exist a quantum spatial search
()=(,t(G);,(G),θ(G)). Let h be an attack defined on . We say that the
efficiency of the attack is almost surely at least E_n iff

    (_h,()≥ E_n| ∈_n)
     1.


The above definition can be naturally applied to strong efficiency. 




§ ATTACKS ON QUANTUM SPATIAL SEARCH ALGORITHMS







We consider the formation of exceptional configurations as a
method of attacking quantum spatial search. 


We will consider the attacks altering the set of marked vertices only. For
quantum spatial search (SzQW,t;,{v}, P_u), we add marked
vertices in such a way that the newly generated set  S' ⊃{v} forms a
connected exceptional configuration. As the probability of finding any vertex
from EC is much lower than the probability of finding a single marked vertex
<cit.>, we decrease the success probability of the
algorithm.

Suppose that the algorithm outputs a vertex from S'∖{v}. Since we
choose additional marked vertices from close neighbourhood of the original 
marked vertex v, the possible defence against the attack is to make a simple
classical search over its neighbourhood, which is efficient for sparse graphs.
However, the cumulated success probability of measuring any of S' is small.
Hence, the attack is effective.

Let us analyse , , and models. For we choose the probability of
adding edge p=2log(n)/n, for we select initial degree K=⌈
2log n⌉ and randomness β =0.5 <cit.>, and for
we set attachment parameter to m_0=3 <cit.>. First, we analyse the probability that for randomly
chosen vertex v we can construct an exceptional configuration S such that
v∈ S. Next, we analyse the efficiency of the attack.




Numerical results demonstrate that for every vertex of graph we can almost
surely find an exceptional configuration of order 3 (3EC), see
Fig. <ref>. Thus the model can be attacked almost surely for any
vertex. This is no longer the case when we allow constructing an exceptional
configuration of order 2 only.
 For and models, even 3EC will not provide
this kind of advantage for the attacker. Nevertheless, the probability of
attacking is still large, and the attacker may be able to construct an
exceptional configuration of a higher order.

Another constraint for resources available to the attacker is the distance between the originally marked vertices and the newly marked ones.
We consider two scenarios. For local exceptional configurations, the new vertices are direct neighbours of the original vertex. In the global scenario, they are at most neighbours of neighbours.
Based on Fig. <ref>, one can see that it is much easier to find global exceptional 
configurations than the local ones for model. Hence the probability of 
attacking increases if the attacked has the ability to use such EC.
For model the attacker cannot utilize 
this type of advantage, for given parametrization. Furthermore, for 
p=ω(log(n)/n) all vertices have almost equal degrees 
<cit.>. This makes finding path graph 3EC impossible, as 
degree condition from Preliminaries section cannot be fulfilled. We have not 
observed any dependence for model.















For analysing the efficiency of the attack, we have chosen at random two 
vertices forming an exceptional configuration. We have analyzed 50 graphs for each order 
n=100, 150,…, 2400 for all models, using the optimization algorithm implemented in QuantumWalk package [Code available at <https://github.com/QuantumWalks/QuantumWalk.jl>] with 
penalty time t_ pen=⌈log(n) ⌉. Parameter t_ pen is a 
value which is added to the time, thus changing the expected time into 
(t+t_ pen)/p. Such adjustment prevents the optimization algorithm from 
halting at small time. Since log(n) is typically much smaller than t, its 
impact on our results is negligible.

In order to asses the impact of the attack on the complexity of quantum spatial search we have calculated the  expected runtime 
for three cases for each random graph. In the first case, which represents the reference search, we have a single marked element. This case provides the value of efficiency of the search 𝒯_ for a given graph. Next, we execute the  on the graph modified by the addition of a single marked element, which results in the formation of an exceptional configuration. This case provides us the value of the increase of the expected run-time resulting from the attack, and thus the efficiency of the attack (cf.  Eq. (<ref>)). Finally, we calculate the expected run-time for the case when the user is aware of the attack and can utilize this knowledge to minimize its effects. In this case we calculate the strong efficiency (cf. Eq. <ref>).


Numerical results presented in Fig. <ref> show that
the attacking efficiency depends on the chosen graph model. Left three plots show that if user is not aware of the attack, the efficiency is almost surely 0.8 for and almost surely 0.9 for . For the results are much more irregular, and no level of efficiency can be guaranteed. This suggests there are some other parameters influencing the efficiency of the attack.

If the user is aware of the attack, it is possible to prevent it at least
partially for all models by changing the measurement time. The efficiency in
this case is captured by the notion of strong  efficiency. For and
models the strong efficiency is almost surely at least 0.5. For we still
observe high irregularity in obtained data and the strong efficiency is
almost surely significantly smaller than 1.


As the complexity attack should result in the algorithm complexity growth, we
have determined numerically the expected time change in the case of common
measurement time. The results are presented in
Fig. <ref>. We have assumed that the complexity grows as the power complexity, Θ(n^α). The tangent of the regression line of the expected run-time in the function of the graph order on the log-log scale provides the approximation of the parameter α. The observed growth of the values of α, resulting from the attack, demonstrates that the attacker is able to significantly increase the expected run-time of the quantum algorithm. This suggests that the algorithm is vulnerable to the complexity attack, which might result in the denial-of-service of the quantum computer. 






§ SUMMARY AND DISCUSSION



In this paper we have signified the problem of possible vulnerability of 
quantum algorithms to the complexity attacks. The presented approach is based 
on the analysis of input data. As such it can be used to discover 
weaknesses of quantum computers resulting from the application of quantum 
algorithms on input data unsuitable for processing on quantum 
machines. This is contrast to the common approach where only the theoretical 
computational complexity is taken into account.

We have developed the theoretical framework for quantifying the efficiency of 
the attacks. We have constructed an attack based on exceptional configurations 
and analysed it in the context of its applicability and efficiency. The 
analysis confirms that it is possible  to decrease the efficiency of quantum 
spatial search based on Szegedy walk by malicious modification of input data. 

One should note that the presented results can be applied for a general 
class of graphs. This is in contrast to the results from 
<cit.>, where only special classes of graphs were 
considered. For those classes it can be shown analytically that the algorithm 
complexity changes from Θ(√(n)) to Θ(n).

It should be stressed that the models of random graphs used for assessing the
security of quantum algorithms mimic the structure of real-world
data <cit.>. As such the presented analysis confirms that
the theoretical security of quantum procedures can be inadequate when the
algorithms are applied for specific input data. This includes input data which
encode the connections observed in complex networks.


We should also stress that the scenario considered in this work does not focus
on the security of the communication which takes place between the client and
the server. On the contrary, our figure of merit is the impact of the modified
data on the  computational resource used by the server. This is in contrast to
the protocols based on the concept of Universal Blind Quantum
Computation <cit.>. Such protocols enable the detection
of the input data modification, if the data are encoded in a quantum state.
Alice can use such protocols to counteract the effect of data alteration by
informing Bob about the Eve's activity. However, such protocol cannot be used to
prevent Alice from sending malformed input data. On the other hand in our
scenario it is easy to include the possibility that Alice is responsible for
sending data which are already malformed – either on purpose or by accident –
and our goal is to asses how often such situation can occur when we consider
data modeled by complex networks. Our results show that secure transmission is
insufficient for ensuring the availability of the quantum hardware.




  
Acknowledgments The authors would like to thank Nikolay Nahimov for
discussion concerning exceptional configurations and Alexander Rivosh for
inspiring the application of this concept in quantum spatial search, and Iza
Miszczak for reviewing the manuscript. This work has been partially supported by
Polish National Science Center grant 2011/03/D/ST6/00413. Numerical calculations
were possible thanks to the support of PL-Grid Infrastructure. We would also
like to thank the anonymous reviewer for his comments, which greatly improved
the quality of our paper.

		

ieeetr


	
