Relevant bibliographies by topics / Quantum query complexity

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Quantum query complexity'

Author: Grafiati
Published: 4 June 2021
Last updated: 5 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Quantum query complexity.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Quantum query complexity"

1

Sardharwalla, Imdad S. B., Sergii Strelchuk, and Richard Jozsa. "Quantum conditional query complexity." Quantum Information and Computation 17, no. 7&8 (2017): 541–67. http://dx.doi.org/10.26421/qic17.7-8-1.

Full text
Abstract:
We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n
APA, Harvard, Vancouver, ISO, and other styles
2

Montanaro, Ashley. "Nonadaptive quantum query complexity." Information Processing Letters 110, no. 24 (2010): 1110–13. http://dx.doi.org/10.1016/j.ipl.2010.09.009.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Montanaro, Ashley, Harumichi Nishimura, and Rudy Raymond. "Unbounded-error quantum query complexity." Theoretical Computer Science 412, no. 35 (2011): 4619–28. http://dx.doi.org/10.1016/j.tcs.2011.04.043.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Ambainis, Andris, and Ronald de Wolf. "Average-case quantum query complexity." Journal of Physics A: Mathematical and General 34, no. 35 (2001): 6741–54. http://dx.doi.org/10.1088/0305-4470/34/35/302.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Montanaro, Ashley, Richard Jozsa, and Graeme Mitchison. "On Exact Quantum Query Complexity." Algorithmica 71, no. 4 (2013): 775–96. http://dx.doi.org/10.1007/s00453-013-9826-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Ambainis, A., A. M. Childs, F. Le Gall, and S. Tani. "The quantum query complexity of certification." Quantum Information and Computation 10, no. 3&4 (2010): 181–89. http://dx.doi.org/10.26421/qic10.3-4-1.

Full text
Abstract:
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced \nand formula. We show that the query complexity is $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
APA, Harvard, Vancouver, ISO, and other styles
7

Beame, Paul, and Widad Machmouchi. "The quantum query complexity of AC0." Quantum Information and Computation 12, no. 7&8 (2012): 670–76. http://dx.doi.org/10.26421/qic12.7-8-11.

Full text
Abstract:
We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $\Theta(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $\Omega(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $\Omega ((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $\Omega(n^{2/3})$ lower bound for the element distinctness problem.
APA, Harvard, Vancouver, ISO, and other styles
8

Li, Tongyang, and Xiaodi Wu. "Quantum Query Complexity of Entropy Estimation." IEEE Transactions on Information Theory 65, no. 5 (2019): 2899–921. http://dx.doi.org/10.1109/tit.2018.2883306.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Ambainis, Andris. "Polynomial degree vs. quantum query complexity." Journal of Computer and System Sciences 72, no. 2 (2006): 220–38. http://dx.doi.org/10.1016/j.jcss.2005.06.006.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Copeland, Daniel, and Jamie Pommersheim. "Quantum query complexity of symmetric oracle problems." Quantum 5 (March 7, 2021): 403. http://dx.doi.org/10.22331/q-2021-03-07-403.

Full text
Abstract:
We study the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a t-query quantum algorithm in terms of group characters. As an application, we show that Ω(n) queries are required to identify a random permutation in Sn. More generally, suppose H is a fixed subgroup of the group G of oracles, and given access to an oracle sampled uniformly from G, we want to learn which coset of H the oracle belongs to. We call this problem
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Quantum query complexity"

1

Preda, Daniel C. (Daniel Ciprian) 1979. "Quantum query complexity revisited." Thesis, Massachusetts Institute of Technology, 2003. http://hdl.handle.net/1721.1/29689.

Full text
Abstract:
Thesis (M.Eng. and S.B.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.<br>Includes bibliographical references (leaves 30-31).<br>In this thesis, we look at the polynomial method for quantum query complexity and relate it to the BQPA = PA question for a random oracle A. We will also look at some open problems and improve some bounds relating classical and quantum complexity.<br>by Daniel C. Preda.<br>M.Eng.and S.B.
APA, Harvard, Vancouver, ISO, and other styles
2

Ben, David Shalev. "Quantum speedups in query complexity." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/113996.

Full text
Abstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 135-141).<br>In this thesis, we study randomized and quantum algorithms in the query complexity model. We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting. We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm. In the pr
APA, Harvard, Vancouver, ISO, and other styles
3

Kawachi, Akinori. "Studies on quantum query complexity and quantum computational cryptography." 京都大学 (Kyoto University), 2004. http://hdl.handle.net/2433/145315.

Full text
Abstract:
Kyoto University (京都大学)<br>0048<br>新制・課程博士<br>博士(情報学)<br>甲第11157号<br>情博第132号<br>新制||情||30(附属図書館)<br>22726<br>UT51-2004-R32<br>京都大学大学院情報学研究科通信情報システム専攻<br>(主査)教授 岩間 一雄, 教授 福嶋 雅夫, 教授 北野 正雄<br>学位規則第4条第1項該当
APA, Harvard, Vancouver, ISO, and other styles
4

Teruyama, Junichi. "Studies on Quantum Query Complexity for Oracle Identification Problems." 京都大学 (Kyoto University), 2013. http://hdl.handle.net/2433/174854.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Lin, Han-Hsuan. "Topics in quantum algorithms : adiabatic algorithm, quantum money, and bomb query complexity." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/99300.

Full text
Abstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2015.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 111-115).<br>In this thesis, I present three results on quantum algorithms and their complexity. The first one is a numerical study on the quantum adiabatic algorithm( QAA) . We tested the performance of the QAA on random instances of MAX 2-SAT on 20 qubits and showed 3 strategics that improved QAA's performance, including a counter intuitive strategy of decreasing the overall evolution time. The second result is a security p
APA, Harvard, Vancouver, ISO, and other styles
6

Brandeho, Mathieu. "New bounds for information complexity and quantum query complexity via convex optimization tools." Doctoral thesis, Universite Libre de Bruxelles, 2018. https://dipot.ulb.ac.be/dspace/bitstream/2013/277139/4/Main.pdf.

Full text
Abstract:
Cette thèse rassemble trois travaux sur la complexité d'information et sur la complexité en requête quantique. Ces domaines d'études ont pour points communs les outils mathématiques pour étudier ces complexités, c'est-à-dire les problèmes d'optimisation.Les deux premiers travaux concernent le domaine de la complexité en requête quantique, en généralisant l'important résultat suivant: dans l'article cite{LMRSS11}, leurs auteurs parviennent à caractériser la complexité en requête quantique, à l'aide de la méthode par adversaire, un programme semi-définie positif introduit par A. Ambainis dans ci
APA, Harvard, Vancouver, ISO, and other styles
7

Magnin, Loick. "Two-player interaction in quantum computing : cryptographic primitives & query complexity." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00676922.

Full text
Abstract:
This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ''quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and pe
APA, Harvard, Vancouver, ISO, and other styles
8

Magnin, Loïck. "Two-player interaction in quantum computing : cryptographic primitives & query complexity." Thesis, Paris 11, 2011. http://www.theses.fr/2011PA112275/document.

Full text
Abstract:
Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étu
APA, Harvard, Vancouver, ISO, and other styles
9

Magnin, Loïck C. A. "Two-player interaction in quantum computing: cryptographic primitives and query complexity." Doctoral thesis, Universite Libre de Bruxelles, 2011. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209783.

Full text
Abstract:
Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.<p><p>Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification.<p><p>La première primitive est la "mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il est possible d'avoir une sécurité lorsque les deux parties sont soumises à certaines contraintes addition
APA, Harvard, Vancouver, ISO, and other styles
10

"Quantum strategic game and quantum query complexity." 2012. http://library.cuhk.edu.hk/record=b5549178.

Full text
Abstract:
本論文研究兩個有關量子計算理論中的問題，其一為量子博弈論，其二為量子查詢複雜度。<br>博弈論於經濟學、計算機科學、生物學、數學等領域中皆為一門重要課題，近年越來越多有關的研究都把焦點放於量子博弈論之上。本論文的第一部份，我們研究由張氏於2010 年提出的量子策略博弈模型。其中研究重點在於某特定類型的博弈中，計算使用量子策略比經典策略多出的優勢。我們成功建構出一個特定的博弈，並証明使用量子策略比經典策略多出的優勢跟策略的多少成線性關係。<br>本論文的第二部份，主要研究有關量子查詢複雜度，它提供一個簡單的框架，用於理解量子力學的計算能力和限制。我們研究的重點在於量子的安得拉-卡普-羅森伯格猜想，那是關於決定某一類圖特性所需的量子查詢複雜度。我們將會介紹施氏與張氏的猜想、布爾函數分析及查詢複雜度研究中重要的研究結果。我們嘗試証明施氏與張氏的猜想，並於最後提出一個有關布爾函數塊敏感度，影響度及方差值的猜想。<br>We study two problems, one in quantum game theory and another in quantum query complexity.<br>Game theory is an important research topic in many elds like economics, computer sciences, bio
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Quantum query complexity"

1

Montanaro, Ashley, Harumichi Nishimura, and Rudy Raymond. "Unbounded-Error Quantum Query Complexity." In Algorithms and Computation. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-92182-0_80.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ambainis, Andris, and Ronald de Wolf. "Average-Case Quantum Query Complexity." In STACS 2000. Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-46541-3_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Zheng, Shenggen, and Daowen Qiu. "From Quantum Query Complexity to State Complexity." In Computing with New Resources. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-13350-8_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Dürr, Christoph, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. "Quantum Query Complexity of Some Graph Problems." In Automata, Languages and Programming. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-27836-8_42.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kawachi, Akinori, Kenichi Kawano, François Le Gall, and Suguru Tamaki. "Quantum Query Complexity of Unitary Operator Discrimination." In Lecture Notes in Computer Science. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-62389-4_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Berzina, Aija, Andrej Dubrovsky, Rusins Freivalds, Lelde Lace, and Oksana Scegulnaja. "Quantum Query Complexity for Some Graph Problems." In SOFSEM 2004: Theory and Practice of Computer Science. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24618-3_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Childs, Andrew M., Shelby Kimmel, and Robin Kothari. "The Quantum Query Complexity of Read-Many Formulas." In Algorithms – ESA 2012. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33090-2_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ambainis, Andris, Kazuo Iwama, Masaki Nakanishi, et al. "Quantum Query Complexity of Boolean Functions with Small On-Sets." In Algorithms and Computation. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-92182-0_79.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Ambainis, Andris, Jānis Iraids, and Daniel Nagaj. "Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$." In SOFSEM 2017: Theory and Practice of Computer Science. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-51963-0_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Jeffery, Stacey, Robin Kothari, and Frédéric Magniez. "Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision." In Automata, Languages, and Programming. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31594-7_44.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Quantum query complexity"

1

Lee, Troy, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. "Quantum Query Complexity of State Conversion." In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2011. http://dx.doi.org/10.1109/focs.2011.75.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

AMBAINIS, ANDRIS. "UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY." In International Congress of Mathematicians 2018. WORLD SCIENTIFIC, 2019. http://dx.doi.org/10.1142/9789813272880_0181.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Vasilieva, Alina. "Quantum versus classical query complexity of relation." In 2011 Seventh International Conference on Natural Computation (ICNC). IEEE, 2011. http://dx.doi.org/10.1109/icnc.2011.6022357.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bahadur, A., C. Dürr, T. Lafaye, and R. Kulkarni. "Quantum query complexity in computational geometry revisited." In Defense and Security Symposium, edited by Eric J. Donkor, Andrew R. Pirich, and Howard E. Brandt. SPIE, 2006. http://dx.doi.org/10.1117/12.661591.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Lee, Troy, and Jeremie Roland. "A Strong Direct Product Theorem for Quantum Query Complexity." In 2012 IEEE Conference on Computational Complexity (CCC). IEEE, 2012. http://dx.doi.org/10.1109/ccc.2012.17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Aaronson, Scott, Daniel Grier, and Luke Schaeffer. "A Quantum Query Complexity Trichotomy for Regular Languages." In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2019. http://dx.doi.org/10.1109/focs.2019.00061.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bansal, Nikhil, and Makrand Sinha. "k-forrelation optimally separates Quantum and classical query complexity." In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2021. http://dx.doi.org/10.1145/3406325.3451040.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Sherstov, Alexander A., Andrey A. Storozhenko, and Pei Wu. "An optimal separation of randomized and Quantum query complexity." In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2021. http://dx.doi.org/10.1145/3406325.3451019.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Sherstov, Alexander A. "Strong direct product theorems for quantum communication and query complexity." In the 43rd annual ACM symposium. ACM Press, 2011. http://dx.doi.org/10.1145/1993636.1993643.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ambainis, Andris, and Ronald de Wolf. "How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?" In 2013 IEEE Conference on Computational Complexity (CCC). IEEE, 2013. http://dx.doi.org/10.1109/ccc.2013.26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Quantum query complexity' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography