Search results for "query"
showing 10 items of 125 documents
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…
Recent Developments in Quantum Algorithms and Complexity
2014
We survey several recent developments in quantum algorithms and complexity: Reichardt’s characterization of quantum query algorithms via span programs [15]; New bounds on the number of queries that are necessary for simulating a quantum algorithm that makes a very small number of queries [2]; Exact quantum algorithms with superlinear advantage over the best classical algorithm [4].
Ultrametric Vs. Quantum Query Algorithms
2014
Ultrametric algorithms are similar to probabilistic algorithms but they describe the degree of indeterminism by p-adic numbers instead of real numbers. This paper introduces the notion of ultrametric query algorithms and shows an example of advantages of ultrametric query algorithms over deterministic, probabilistic and quantum query algorithms.
Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection
2015
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph $(V,E)$ and access to a function $f:V\rightarrow \{0,1\}$ as a black box. We are asked to determine if there exist $(u,v) \in E$, such that $f(u)=f(v)=1$. In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial ($\Omega(\sqrt{n})$ and $\Omega(n)$, respectively) and there is no known matching upper …
Quantum versus classical query complexity of relation
2011
This paper investigates the computability of mathematical relations in a quantum query model. The important task in complexity theory is to find examples with a large gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design that allow achieving a large separation between classical and quantum query complexity of a specific relation. We demonstrate an example where quantum query algorithm for a finite relation needs more than two times fewer queries than the best possible classical analogue. We also show that relation can be extended to infinite family of relations with an input of general size N.
Multimedia Retrieval in a Medical Image Collection: Results Using Modality Classes
2013
The effective communication between user and systems is one main aim in the Multimedia Information Retrieval field. In this paper the modality classification of images is used to expand the user queries within the ImageCLEF Medical Retrieval collection provided by organizers. Our main contribution is to show how and when results can be improved by understanding modality-related challenges. To do so, a detailed analysis of the results of the experiments carried out is presented and the comparison between these results shows that the improvement using modality class query expansion is query-dependent.
A query language for medical statistical analysis
1991
While standard query languages support primarily the definition of single queries, in the evaluation of medical studies one usually formulates large sets of interdependent queries. A set of this type is called an integrated transaction. Our system for the definition of integrated transactions is based on the observation that in medicine a large number of statistical evaluations is founded on a conceptional model that can be structured as a tree. We describe a screen oriented tree editor for the relational data base system DBase and report on our experience with its application in the evaluation of the success rate of PTCA interventions.
What to Expect and What to Focus on in SQL Query Teaching
2019
In the process of learning a new computer language, writing erroneous statements is part of the learning experience. However, some errors persist throughout the query writing process and are never corrected. Structured Query Language (SQL) consists of a number of different concepts such as expressions, joins, grouping and ordering, all of which by nature invite different possible errors in the query writing process. Furthermore, some of these errors are relatively easy for a student to fix when compared to others. Using a data set from three student cohorts with the total of 744 students, we set out to explore which types of errors are persistent, i.e., more likely to be left uncorrected by…
The Effects of Database Complexity on SQL Query Formulation (journal-first)
2020
The learning of practical Structured Query Language (SQL) skills often takes place in digital environments, where the learner writes queries against an exercise database. The exercise database is usually designed and implemented by the teacher, and populated with makeshift data. Although this approach is common, and SQL taught in almost all database courses, little scientific attention has been given to the nature of the exercise database.
SQL Education
2020
Structured Query Language (SQL) skills are crucial in software engineering and computer science. However, teaching SQL effectively requires both pedagogical skill and considerable knowledge of the language. Educators and scholars have proposed numerous considerations for the betterment of SQL education, yet these considerations may be too numerous and scattered among different fora for educators to find and internalize, as no systematic mappings or literature reviews regarding SQL education have been conducted. The two main goals of this mapping study are to provide an overview of educational SQL research topics, research types, and publication fora, and to collect and propagate SQL teachi…