Search results for "Search problem"
showing 10 items of 12 documents
Grover’s Algorithm with Errors
2013
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].
Exceptional Quantum Walk Search on the Cycle
2016
Quantum walks are standard tools for searching graphs for marked vertices, and they often yield quadratic speedups over a classical random walk's hitting time. In some exceptional cases, however, the system only evolves by sign flips, staying in a uniform probability distribution for all time. We prove that the one-dimensional periodic lattice or cycle with any arrangement of marked vertices is such an exceptional configuration. Using this discovery, we construct a search problem where the quantum walk's random sampling yields an arbitrary speedup in query complexity over the classical random walk's hitting time. In this context, however, the mixing time to prepare the initial uniform state…
Discrete-mathematical approach to formal description of measurement procedure
1996
The discrete-mathematical model of measurement procedure is developed for facilitating the description of measurements in both quantitative and qualitative scales. On the basis of this model the Measurement Problem is formulated. It is shown that the problem can be considered, in the general case, as one of the discrete optimization problems. The suggested approach brings closer the concepts of a computing algorithm and measurement procedure so that it permits the application of similar tools for the analysis and development of both of them.
Optimality conditions for shakedown design of trusses
1995
This paper deals with optimal shakedown design of truss structures constituted by elastic perfectly plastic material. The design problem is formulated by means of a statical approach on the grounds of the shakedown lower bound theorem, and by means of a kinematical approach on the grounds of the shakedown upper bound theorem. In both cases two different types of design problem are formulated: one searches for the minimum volume design whose shakedown limit load is assigned; the other searches for the maximum shakedown limit load design whose volume is assigned. The Kuhn-Tucker equations of the four problems here above mentioned are found by utilizing a variational approach; these equations …
A novel technique for stochastic root-finding: Enhancing the search with adaptive d-ary search
2017
The most fundamental problem encountered in the field of stochastic optimization, is the Stochastic Root Finding (SRF) problem where the task is to locate an unknown point x∗ for which g(x∗) = 0 for a given function g that can only be observed in the presence of noise [15]. The vast majority of the state-of-the-art solutions to the SRF problem involve the theory of stochastic approximation. The premise of the latter family of algorithms is to oper ate by means of so-called “small-step”processesthat explorethe search space in a conservative manner. Using this paradigm, the point investigated at any time instant is in the proximity of the point investigated at the previous time instant, render…
Optimal Design of Trusses According to a Plastic Shakedown Criterion
2004
The optimal design of elastic-perfectly plastic truss structures subjected to quasi-statically loads variable within a given load domain is studied. The actions are given as the combination of fixed load and perfect cyclic load. Suitably chosen load multipliers are given. A minimum volume formulation of the design problem with assigned limit load multiplier is developed and it is provided on the grounds of a statical approach as well as of a kinematical approach. The incremental collapse (ratchetting) of the optimal structure is prevented, as long as the loads are not greater than some prescribed values, by special constraints suitably introduced in the search problem. The Kuhn-Tucker equat…
Structural Knowledge Extraction from Mobility Data
2016
Knowledge extraction has traditionally represented one of the most interesting challenges in AI; in recent years, however, the availability of large collections of data has increased the awareness that “measuring” does not seamlessly translate into “understanding”, and that more data does not entail more knowledge. We propose here a formulation of knowledge extraction in terms of Grammatical Inference (GI), an inductive process able to select the best grammar consistent with the samples. The aim is to let models emerge from data themselves, while inference is turned into a search problem in the space of consistent grammars, induced by samples, given proper generalization operators. We will …
Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
2015
In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the "simplex of $K_M$ complete graphs" with all configurations of two marked vertices, two configurations of $M+1$ marked vertices, and two configurations of $2(M+1)$ marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration's value can cause the search to fail. This sensitivity to the jumping rate is an is…
Grover’s Search with Faults on Some Marked Elements
2018
Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze…
Grover’s Search with Faults on Some Marked Elements
2016
Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size N using $$O\sqrt{N}$$ queries. It provides a significant speed-up over any classical algorithm [2]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [1, 4]. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in $$O\sqrt{N}$$ queries.