Quantum abstract detecting systems
- PDF / 1,011,742 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 201 Views
Quantum abstract detecting systems Elías F. Combarro1 · José Ranilla1 · Ignacio Fernández Rúa2 Received: 12 December 2019 / Accepted: 11 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study Quantum Abstract Detecting Systems (QADS), that generalize some key characteristics of the operators used in Grover’s algorithm, a wide variety of quantum walks and the quantum abstract search algorithm. A QADS is an algorithm that constructs a quantum state and a quantum operator that help testing whether a circuit-implemented boolean function f is identically zero. We also identify some relatively weak properties of QADS that lead to the construction of algorithms for the detection problem (i.e. determining whether there is a marked element in a given set). Our results provide not only a common framework to all the aforementioned search methods, and their transformation into algorithms for the detection problem, but also allow the development of new similar methods. As an example, we construct a modification of Grover’s algorithm (from the tensor product of controlled QADS) that shows improved detection probability. Keywords Quantum detection · Quantum search · Quantum walks · Grover search
1 Introduction It is well-known that quantum computation outperforms classical computation when searching in an unsorted database, i.e., finding a marked element in a list of unordered ones. The first quant quantum algorithm solving this problem was Grover’s algorithm [9], where the elements of the list are marked by the evaluation of a boolean function f (i.e., x is marked iff f (x) = 1). A quantum oracle O evaluating such a function
B
Ignacio Fernández Rúa [email protected] Elías F. Combarro [email protected] José Ranilla [email protected]
1
Computer Science Department, University of Oviedo, Oviedo, Spain
2
Mathematics Department, University of Oviedo, Oviedo, Spain 0123456789().: V,-vol
123
258
Page 2 of 25
E. F. Combarro et al.
f is combined with an amplitude amplification operator G for marked elements, to achieve quadratic speed-up over the best classical algorithm on the oracle model. Namely, given the function f , Grover’s algorithm constructs a uniform superposition initial state |ψ0 , and a quantum operator U = G O, product of the quantum oracle and the diffusion operator G. Such an operator can be used to evolve the quantum system from the initial state, so that measurement of the resulting state yields a marked element with high probability. A related problem is that of detecting the existence of marked elements. It is clear that if an element is found by a searching algorithm, the detection problem is implicitly solved. However, there are some situations where finding a particular marked element is not strictly necessary. For instance, when studying the commutativity of an algebra described by a multiplication table it is enough to detect the existence of a nonmatching pair of constants to guarantee that the algebra is noncommutative [4]. In this context
Data Loading...
