Fetching the paper…
Reading the bibliography…
This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model.
M. Snir. Lower bounds on probabilistic linear decision trees. Theoret. Comput. Sci
1985
Earlier work this paper cites.
R. Dramanac and R. Crkvenjakov. DNA sequencing by hybridization. Yugoslav Patent Application 570
1987
Earlier work this paper cites.
Y. P. Lysov, V. L. Florent’ev, A.A. Khorlin, K. Khrapko, V. V. Shik and A. D. Mirzabekov. DNA Sequencing by hybridization with oligonucleotides. A novel method. Dokl. Acad. Sci USSR
1988
Earlier work this paper cites.
P A. Pevzner and R. J. Lipshutz. Towards DNA sequencing chips. In Proc. 19th MFCS
1994
Earlier work this paper cites.
S. S. Skiena and G. Sundaram. Reconstructing strings from substrings. J. Computational Biol
1995
Earlier work this paper cites.
L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. 28th STOC
1996
Earlier work this paper cites.
E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput
1997
Earlier work this paper cites.
P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput
1997
Earlier work this paper cites.
M. Boyer, G. Brassard, P. Høyer and A. Tapp. Tight bounds on quantum searching. Fortschritte Der Physik
1998
Cited alongside, same era.
W. van Dam. Quantum oracle interrogation: Getting all information for almost half the price. In Proc. 39th FOCS
1998
Cited alongside, same era.
A. Ambainis. A note on quantum black-box complexity of almost all Boolean functions. Inf. Process. Lett
1999
Cited alongside, same era.
A. Ambainis. A better lower bound for quantum algorithms searching an ordered list. In Proc. 40th FOCS
1999
Cited alongside, same era.
H. Buhrman and R. de Wolf. A lower bound for quantum search of an ordered list. Inf. Process. Lett
1999
Cited alongside, same era.
R. Beals, H. Buhrman, R. Cleve, M. Mosca and R. de Wolf. Quantum lower bounds by polynomials. J. ACM
H. Ramesh and V. Vinay. String matching in O ~ ( n + m ) \tilde{O}(\sqrt{n}+\sqrt{m}) quantum time. J. Discrete Algorithms
2003
Later among the works it cites.
S. Zhang. On the power of Ambainis lower bounds. Theoret. Comput. Sci
2005
Later among the works it cites.
R. Špalek and M. Szegedy. All quantum adversary methods are equivalent. Theory of Computing
2006
Later among the works it cites.
A. M. Childs, A. J. Landahl and P. A. Parrilo. Improved quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A
2007
Later among the works it cites.
M. Ben-Or and A. Hassidim. The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In Proc. 49th FOCS
2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2001
Cited alongside, same era.
A. Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci
2002
Cited alongside, same era.
P. Høyer, J. Neerbek and Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica
2002
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. A limit on the speed of quantum computation for insertion into an ordered list. arXiv:quant-ph/9812057
Cited in the paper.
E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. Invariant quantum algorithms for insertion into an ordered list. arXiv:quant-ph/9901059
Cited in the paper.
A. M. Childs and T. Lee. Optimal quantum adversary lower bounds for ordered search. In Proc. 35th ICALP
2008
Later among the works it cites.
K. Iwama, H. Nishimura, R. Raymond and J. Teruyama. Quantum counterfeit coin problems. In Proc. 21st ISAAC
2010
Later among the works it cites.