Last Update
10.08.2016 |

[1] Andris Ambainis, Ronald de Wolf. How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Computational Complexity 23(2), pp. 305-322 (2014)

[2] Aleksandrs Belovs, Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound, Computational Complexity, 24(2), pp. 255-293, 2015, earlier version at IEEE Conference on Computational Complexity 2014

[3] Scott Aaronson, Andris Ambainis. The Need for Structure in Quantum Speedups. Theory of Computing 10, pp. 133-166 (2014)

[4] Andris Ambainis, Ashley Montanaro. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information & Computation 14(5-6), pp. 439-453 (2014)

[5] Andris Ambainis, Jozef Gruska, Shenggen Zheng. Exact query complexity of some special classes of Boolean functions. Quantum Information & Computation 14(5-6), pp. 435-452 (2015)

[6] Andris Ambainis, Renato Portugal, Nikolay Nahimov. Spatial search on grids with minimum memory, Quantum Information and Computation, 15 (13/14), pp. 1233-1247, 2015.

[7] Andris Ambainis, Thomas G. Wong. Correcting for potential barriers in quantum walk search, Quantum Information and Computation, 15 (15/16), pp. 1365-1372, 2015.

[8] Thomas G. Wong, Andris Ambainis. Quantum search with multiple walk steps per oracle query, Physical Review A, 92(2), article 022338, 2015

[9] Thomas G. Wong. Faster quantum walk search on a weighted graph, Physical Review A, 92(3), article 032320, 2015.

[10] Manik Banik, Some Sankar Bhattacharya, Amit Mukherjee, Arup Roy, Andris Ambainis, Ashutosh Rai. Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound, Physical Review A, 92(3), article 030103, 2015.

[11] Thomas G. Wong, David A. Meyer. Irreconcilable difference between quantum walks and adiabatic quantum computing. Physical Review A, 93(6), article 062313.

[12] Thomas G. Wong, P. Philipp. Engineering the Success of Quantum Walk Search Using Weighted Graphs. Physical Review A 94, 022304 (2016)

[13] Thomas G Wong, Quantum walk search with time-reversal symmetry breaking. Journal of Physics A, 48 (40), article 405303, 2015.

[14] Thomas G Wong, Grover search with lackadaisical quantum walks, Journal of Physics A, 48(43), article 435304, 2015.

[15] Thomas G Wong. Quantum walk search on Johnson graphs. Journal of Physics A, 49(19), article 195303, 2016.

[16] Thomas G. Wong. Diagrammatic approach to quantum search. Quantum Information Processing, 14(6), pp. 1767-1775, 2015.

[17] Thomas G. Wong. Quantum walk on the line through potential barriers. Quantum Information Processing, 15(2), pp. 675-688, 2016.

[18] Thomas G. Wong. Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Information Processing, 15(4), pp.1411-1443, 2016

[19] Thomas G. Wong, Luís Tarrataca, Nikolay Nahimov. Laplacian versus adjacency matrix in quantum walk search. Quantum Information Processing, accepted for publication.

[20] Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser Omar. Spatial Search by Quantum Walk is Optimal for Almost all Graphs. Physical Review Letters, 116(10), article 100501, 2016.

[21] Andris Ambainis, Superlinear Advantage for Exact Quantum Algorithms. SIAM Journal on Computing, 45(2), pp. 617-631, 2016.

[22] Andris Ambainis. On Physical Problems that are Slightly More Difficult than QMA. IEEE Conference on Computational Complexity 2014, pp. 32-43

[23] Andris Ambainis. Recent Developments in Quantum Algorithms and Complexity. Proceedings of DCFS 2014, pp. 1-4

[24] Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian. Weak Parity. Proceedings of ICALP 2014, vol. 1, pp. 26-38

[25] Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo. Tighter Relations between Sensitivity and Other Complexity Measures. Proceedings of ICALP 2014, vol. 1, pp. 101-133

[26] Andris Ambainis, Krisjanis Prusis. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Proceedings of MFCS 2014, vol. 2, pp. 33-44

[27] Andris Ambainis, Ansis Rosmanis, Dominique Unruh, Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 474 - 483, 2014

[28] Scott Aaronson, Andris Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 307-316, 2015.

[29] Andris Ambainis, Yuval Filmus, François Le Gall. Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 585-593, 2015.

[30] Andris Ambainis, Jevgēnijs Vihrovs. Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma. 12th Annual Conference on Theory and Applications of Models of Computation (TAMC), pp. 122-133, 2015.

[31] Agnis Āriņš. Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity, Mathematical and Engineering Methods in Computer Science - 10th International Doctoral Workshop (MEMICS), pp. 35-41, 2015.

[32] Nikolajs Nahimovs, Alexander Rivosh. Exceptional Configurations of Quantum Walks with Grover’s Coin. Mathematical and Engineering Methods in Computer Science - 10th International Doctoral Workshop (MEMICS), pp. 79-92, 2015.

[33] Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf, Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 903-922, 2016.

[34] Nikolajs Nahimovs, Alexander Rivosh. Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations. SOFSEM 2016: Theory and Practice of Computer Science, pp. 381-391, 2016.

[35] Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh. Grover’s Search with Faults on Some Marked Elements. SOFSEM 2016: Theory and Practice of Computer Science, pp. 344-355, 2016.

[36] Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs. Sensitivity Versus Certificate Complexity of Boolean Functions. 11th International Computer Science Symposium in Russia (CSR) pp. 16-28, 2016.

[37] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs. Separations in query complexity based on pointer functions. 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 800-813, 2016.

[38] Andris Ambainis, Martins Kokainis, Robin Kothari. Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. 31st Conference on Computational Complexity (CCC), pp. 4:1-4:14, 2016.

[39] Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. 31st Conference on Computational Complexity (CCC), pp. 25:1-25:19, 2016

[40] Aleksandrs Belovs, Ansis Rosmanis. Adversary Lower Bounds for the Collision and the Set Equality Problems. arxiv:1310.5185.

[41] Thomas G Wong. Quantum Walk Search through Potential Barriers. arXiv:1503.06605

[42] K. Prusis, J. Vihrovs, and T. G. Wong. Doubling the Success of Quantum Walk Search Using Internal-State Measurements. arxiv: 1511.03865

[43] A. Ambainis, K. Prusis, J. Vihrovs, and T. G. Wong. Oscillatory Localization of Quantum Walks by Classical Electric Circuits. arXiv:1606.02136

[44] K. Prusis, J. Vihrovs, and T. G. Wong. Stationary States in Quantum Walk Search. arXiv:1608.00136

[45] Andris Ambainis, Abuzer Yakaryilmaz. Automata and Quantum Computing. arXiv:1507.01988

[46] Andris Ambainis, Dmitry Kravchenko, Ashutosh Rai. Optimal Classical Random Access Codes Using Single d-level Systems. arXiv:1510.03045

[47] Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai. Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities. arXiv:1607.05490

[48] Andris Ambainis, Jānis Iraids, Daniel Nagaj. Exact quantum query complexity of EXACT^{n}k,l. arXiv:1608.02374