On $k$-d Range Search with Patricia Tries
Patricia tries are explored for indexing combined text and spatial data. A combined text and spatial data range search algorithm is presented for reporting all data from a set of size $n$ intersectin...
Patricia tries are explored for indexing combined text and spatial data. A combined text and spatial data range search algorithm is presented for reporting all data from a set of size $n$ intersectin...
Compression in Finite Fields and Torus-Based Cryptography
We present efficient compression algorithms for subgroups of multiplicative groups of finite fields, we use our compression algorithms to construct efficient public key cryptosystems called $\T_2$ an...
We present efficient compression algorithms for subgroups of multiplicative groups of finite fields, we use our compression algorithms to construct efficient public key cryptosystems called $\T_2$ an...
You are not logged in to this journal. Log in
Quantum Property Testing
SIAM J. Comput. Volume 37, Issue 5, pp. 1387-1400 (2008)
Published January 16, 2008
Connotea
CiteULike
del.icio.us
BibSonomy
A language $L$ has a property tester if there exists a probabilistic algorithm that given an input $x$ queries only a small number of bits of $x$ and distinguishes the cases as to whether $x$ is in $L$ and $x$ has large Hamming distance from all $y$ in $L$. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
©2008 Society for Industrial and Applied Mathematics| History: | Received March 23, 2004; accepted June 19, 2007; published January 16, 2008 |
| Permalink: | http://dx.doi.org/10.1137/S0097539704442416 |
KEYWORDS and AMS
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM