Akadēmiskais centrsNew Ideas for Quantum Algorithms
[1] A. Ambainis, R. Portugal, N. Nahimov. Spatial Search on Grids with Minimum Memory. Quantum Information and Computation, 15(13-14): 1233-1247 (2015), arXiv:1312.0172.
[2] H. Krovi, F. Magniez, M. Ozols, J. Roland. Quantum walks can find a marked element on any graph. Algorithmica, published online, 2015.
[3] A. Belovs, A. Childs, S. Jeffery, R. Kothari, F. Magniez.Time-Efficient Quantum Walks for 3-Distinctness, Proceedings of 40th International Colloquium on Automata, Languages and Programming, pp. 105-122, 2013.
[4] S. Jeffery, F. Magniez, R. de Wolf. Optimal parallel quantum query algorithms. 22nd European Symposium on Algorithms, pp. 592-604, 2014.
[5] T. Wong, A. Ambainis. Quantum Search with Multiple Walk Steps per Oracle Query. Physical Review A, 92, 022338 (2015), arXiv:1502.04792.
[6] A. Ambainis, T. Wong. Correcting for Potential Barriers in Quantum Walk Search. Quantum Information and Computation, 15(15-16): 1365-1372 (2015) arXiv:1505.02035.
[7] T. Wong. Quantum Walk Search through Potential Barriers. arXiv:1503.06605.
[8] T. Wong. Grover Search with Lackadaisical Quantum Walks. Journal of Physics A, 48, 435304 (2015), arXiv:1502.04567.
[9] T. Wong. Quantum Walk Search with Time-Reversal Symmetry Breaking. Journal of Physics A, 48, 405303 (2015), arXiv:1504.07375.
[10] T. Wong. Diagrammatic Approach to Quantum Search. Quantum Information Processing, 14(6):1767-1775, 2015.
[11] S. Chakraborty, L. Novo, A. Ambainis, Y. Omar. Spatial search by quantum walk is optimal for almost all graphs. Physical Review Letters 116, 100501 (2016) [HIGHLIGHT]
[12] T. G. Wong, D. A. Meyer. Irreconcilable Di erence Between Quantum Walks and Adiabatic Quantum Computing. Physical Review A, Also arXiv:1603.05423.
[13] T. G. Wong. Quantum Walk Search on Johnson Graphs. Journal of Physics A, 49, 195303 (2016)
[14] T. G. Wong. Quantum Walk on the Line through Potential Barriers. Quantum Information Processing, 15, 675 (2016)
[15] D. Kravchenko, N. Nahimovs, A. Rivosh. Grover's Search with Faults on Some Marked Elements. Proceedings of SOFSEM 2016, pp. 344-355.
[16] N. Nahimovs, A. Rivosh. Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations.Proceedings of SOFSEM 2016, pp. 381-391.
[17] T. G. Wong. Faster Quantum Walk Search on a Weighted Graph. Physical Review A 92, 032320 (2015)
[18] N. Nahimovs, A. Rivosh. Exceptional Con gurations of Quantum Walks with Grover's Coin.Proceedings of MEMICS 2015, pp. 79-92.
[19] R. A. M. Santos. Szegedy's quantum walk with queries. arXiv:1603.05473
[20] T. G. Wong, L. Tarrataca, N. Nahimov. Laplacian versus Adjacency Matrix in Quantum Walk Search. arXiv:1512.05554
[21] K. Prusis, J. Vihrovs, T. G. Wong. Doubling the Success of Quantum Walk Search Using Internal- State Measurements. arXiv:1511.03865
[22] T. G. Wong. Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices.Quantum Information Processing, 15, 1411 (2016)
Learning graphs
[1] A. Belovs, A. Childs, S. Jeffery, R. Kothari, F. Magniez. Time-Efficient Quantum Walks for 3-Distinctness, Proceedings of 40th International Colloquium on Automata, Languages and Programming, pp. 105-122, 2013.
[2] A. Belovs, E. Blais. Quantum Algorithm for Monotonicity Testing on the Hypercube. Theory of Computing 11, 403-412 (2015), arXiv:1503.02868.
[3] S. Jeffery, F. Magniez, and R. de Wolf. Optimal parallel quantum query algorithms. 22nd European Symposium on Algorithms, pp. 592-604, 2014.
[4] A. Ambainis, A. Belovs, O. Regev, R. de Wolf. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 16), pp.903-922. Also accepted for a talk at QIP'16. arXiv:1507.03126
Algorithms for hidden shift problems
[1] T. Decker, G. Ivanyos, M. Santha and P. Wocjan.Hidden symmetry subgroup problem, SIAM Journal on Computing, 42:1987-2007, 2013.
[2] T. Decker, P. Hoyer, G. Ivanyos and M. Santha. Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Information and Computation, 14:790-806, 2014
[3] K. Friedl, G. Ivanyos, F. Magniez, M. Santha and P. Sen. Hidden Translation and Translating Coset in Quantum Computing. SIAM Journal on Computing, 43:1-24, 2014.
[4] T. Decker, G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha. An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group. 39th International Symposium on Mathematical Foundations of Computer Science, pp. 226-238, 2014.
[5] G. Ivanyos and M. Santha, On solving systems of diagonal polynomial equations over finite fieelds. 9th International Frontiers of Algorithmics Workshop, Guilin, pp. 125-137, 2015.
Quantum property testing
[1] A. Montanaro, R. de Wolf. A survey of quantum property testing. To appear as a Graduate Survey in Theory of Computing. arXiv:1310.2035.
[2] A. Ambainis, A. Montanaro. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information and Computation, 14:439-453, 2014.
[3] D. Aharonov, L. Eldar. Quantum locally testable codes. arXiv:1310.5664.
[4] A. Belovs, E. Blais. Quantum Algorithm for Monotonicity Testing on the Hypercube. Theory of Computing 11, 403-412 (2015) arXiv:1503.02868.
[5] S. Aaronson, A. Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Proceedings of STOC'2015,pp.307-316.arXiv:1411.5729.
[6] A. Ambainis, A. Belovs, O. Regev, R. de Wolf. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 16), pp.903-922. Also accepted for a talk at QIP'16. arXiv:1507.03126
[7] A. Belovs, E. Blais. A Polynomial Lower Bound for Testing Monotonicity. Proceedings of the ACM Conference on the Theory of Computing (STOC'16), to appear. arXiv:1511.05053 Other publications [1] D. Gosset, B. M. Terhal, A. Vershynina. Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction. Phys. Rev. Lett. 114, 140501 (2015), arXiv:1409.7745.
[2] M. Brandeho and J. Roland. A universal adiabatic quantum query algorithm. 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC'15), 2015, to appear. arXiv:1409.3558
General properties of quantum algorithms
[1] R. Jozsa, M. Van den Nest. Classical simulation of extended Clifford circuits. Quantum Information and Computation, 14:0633—0648, 2013.
[2] R. Jozsa, A. Miyake, S. Strelchuk. Jordan-Wigner formalism for arbitrary 2-input 2-output match-gates and their classical simulation. Quantum Information and Computation, Vol. 15, No. 7&8 (2015) 0541-0556. arXiv:1311.3046v2.
[3] J. Rashid, A. Yakaryilmaz. Implications of Quantum Automata for Contextuality. Proceedings of the 19th International Conference on Implementation and Application of Automata (CIAA 2014), Lecture Notes in Computer Science, Vol. 8587 (2014) 318-331. arXiv:1404.2761.
[4] A. Acin, S. Pironio, T. Vertesi, P. Wittek. Optimal randomness certi fication from one entangled bit. arXiv:1505.03837.
[5] C. Bamps, S. Pironio. Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing. Phys. Rev. A 91(5), 052111 (2015). arXiv:1504.06960.
[6] J. Bausch, T. Cubitt and M. Ozols. The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension. arXiv:1605.01718.
[7] A. Ambainis, A. Yakaryilmaz. Automata and Quantum Computing. Automata: From Mathematics to Applications, to appear. Also arXiv:1507.01988.
[8] T. Morimae, D. Nagaj, N. Schuch. Quantum proofs can be veri fied using only single qubit measurements.Physical Review A 93, 022326 (2016) Role of structure in quantum algorithms
[1] S. Aaronson, A. Ambainis, K. Balodis, M. Bavarian. Weak Parity. Proceedings of ICALP'2014, accepted for publication. Also arXiv:1312.0036.
[2] A. Ambainis, M. Bavarian, Y. Gao, J. Mao, X. Sun, and S. Zuo, Tighter relations between sensitivity and other complexity measures. Proceedings of ICALP'2014, accepted for publication.
[3] A. Ambainis. Superlinear advantage for exact quantum algorithms. SIAM Journal on Computing 45(2): 617-631 (2016)
[4] A. Ambainis, J. Gruska, S. Zheng. Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Information and Computation, 15(5-6): 435-452 (2015)
[5] A. Ambainis, J. Iraids, J. Smotrovs: Exact Quantum Query Complexity of EXACT and THRESHOLD. Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), pp. 263-269.
[6] A. Ambainis, K. Prūsis. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Proceedings of MFCS'2014, vol. 2, pp. 33-44. arXiv:1402.5078.
[7] A. Ambainis and R. de Wolf. How low can approximate degree and quantum query complexity be for total Boolean functions? Computational Complexity, 23(2):305-322, 2014.
[8] R. Kulkarni and M. Santha. Query complexity of matroids. 8th International Conference on Algorithms and Complexity, Barcelona, Lecture Notes in Computer Science, 7878:300-311, 2013.
[9] S. Aaronson, A. Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Proceedings of STOC'2015, pp. 307-316. arXiv:1411.5729.
[10] A. Ambainis, K. Prusis, J. Vihrovs. Sensitivity versus Certi cate Complexity of Boolean Functions. Computer Science Symposium in Russia (CSR 2016), to appear, arXiv:1503.07691.
[11] A. Ambainis, J. Vihrovs. Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma. Proceedings of TAMC'2015, pp. 122-133
[12] S. Aaronson, A. Ambainis. The Need for Structure in Quantum Speedups. Theory of Computing, 10: 133-166 (2014)
[13] A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, J. Smotrovs. Separations in Query Complexity Based on Pointer Functions. Proceedings of STOC 2016, to appear, also arXiv:1506.04719 (2015)
[14] S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis, J. Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Proceedings of CCC 2016, to appear, also arXiv:1511.08682 (2015)
Quantum lower bounds for specific problems
[1] A. Belovs, A. Rosmanis. Adversary Lower Bounds for the Collision and the Set Equality Problems. arXiv:1310.5185.
[2] A. Ambainis, A. Rosmanis, D. Unruh. Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding. Proceedings of FOCS'2014, pp. 474-483 arXiv:1404.6898.
[3] L. Magnin, J. Roland. Explicit relation between all lower bound techniques for quantum query complexity. International Journal of Quantum Information. To appear (online ready).
[4] A. Belovs. Variations on Quantum Adversary. arXiv:1504.06943.
[5] A. Nayebi, S. Aaronson, A. Belovs, L. Trevisan. Quantum lower bound for inverting a permutation with advice. Quantum Information and Computation, to appear. arXiv:1408.3193.
[6] J. Kaniewski, T. Lee, R. de Wolf. Query complexity in expectation. Proceedings of 42nd International Colloquium on Automata, Languages and Programming (ICALP 15), LNCS 9134, pp.761-772. arXiv:1411.7280.
[7] T. Lee, A. Prakash, H. Yuen, R. de Wolf. On the sum-of-squares degree of symmetric quadratic functions. Proceedings of Computational Complexity Conference (CCC'16), to appear. arXiv:1601.02311
[8] G. Brassard, P. H yer, K. Kalach, M. Kaplan, S. Laplante, L. Salvail. Merkle Puzzles in a Quantum World. Journal of Cryptology, to appear.
[9] F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, D. Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. Random Structures & Algorithms, 48:3,pp. 612-638, 2016.
Algorithms in Quantum Communication
[1] I. Kerenidis, S. Laplante, V. Lerays, J. Roland, D. Xiao. Lower bounds on information complexity via zero-communication protocols and applications. SIAM Journal on Computing, special issue for FOCS 2012. To appear.
[2] I. Kerenidis, M. Lauriere, D. Xiao. New lower bounds for privacy in communication complexity. 7th International Conference on Information Theoretic Security (ICITS), 2013
[3] L. Fontes, R. Jain, I. Kerenidis, M. Lauriere, S. Laplante, J. Roland. Relative Discrepancy does not separate Information and Communication Complexity. To appear in Proceedings of ICALP, 2015.
[4] H. Buhrman, L. Czekaj, A. Grudka, M. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, S. Strelchuk. Quantum communication complexity advantage implies violation of a Bell inequality. arXiv:1502.01058
[5] I. Kerenidis, M. Lauriere, F. Le Gall, M. Rennela. Privacy in Quantum Communication Complexity. Proceedings of Asian Quantum Information Science Conference, 2015, arXiv:1409.8488.
[6] A. Anshu, A. Belovs, S. Ben-David, M. Göös, R. Jain, R. Kothari, T. Lee, M. Santha. Separations in communication complexity using cheat sheets and information complexity. arXiv:1605.01142
Quantum Distributed Computation
[1] N. de Beaudrap and M. Roetteler. Quantum linear network coding as one-way quantum computation. Proceedings of TQC’2014. arXiv:1403.3533
[2] A. Yakaryilmaz, A. C. C. Say and H. G. Demirci. Debates with small transparent quantum veri ers. Developments in Language Theory 327-338 (2014). arXiv:1405.1655
[3] Y. Dulek, C. Schaffner, F. Speelman. Quantum homomorphic encryption for polynomial-sized circuits. Proccedings of CRYPTO'16, to appear. arXiv:1603.09717
Quantum communication and quantum non-locality
[1] S. Pironio. All CHSH polytopes. J. Phys. A: Math. Theor. 47, 424020, 2014 arXiv:1402.6914.
[2] A. Ambainis, J. Iraids. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. Proceedings of TQC'2013, pp. 146-156.
[3] A. Chailloux, I. Kerenidis, J. Sikora. Strong connections between quantum encodings, non-locality and quantum cryptography, Physical Review A, 89:022334, 2014.
[4] A. Chailloux, I. Kerenidis, S. Kundu, J. Sikora. Optimal bounds for parity-oblivious random access codes with applications, Proceedings of TQC’2014, to appear, arXiv:1404.5153.
[5] A. Nieto-Silleras, S. Pironio, J. Silman.Using complete measurement statistics for optimal device-independent randomness evaluation. New Journal of Physics, 16:013035, 2014.
[6] A. Acin, D. Cavalcanti, E. Passaro, S. Pironio, P. Skrzypczyk. Detection attacks on cryptographic protocols and bound randomness. arXiv:1505.00053
[7] A. Acin, S. Pironio, T. Vertesi, P. Wittek. Optimal randomness certi cation from one entangled bit. Physical Review A 93, 040102 (2016).arXiv:1505.03837
[8] C. Bamps, S. Pironio. Sum-of-squares decompositions for a family of CHSH-like inequalities and their application to self-testing. Physical Review A 91, 052111 (2015).arXiv:1504.06960.
[9] H. Buhrman, L. Czekaj, A. Grudka, M. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, S. Strelchuk. Quantum communication complexity advantage implies violation of a Bell inequality. arXiv:1502.01058
[10] E. Woodhead. Tight asymptotic key rate for the Bennett-Brassard 1984 protocol with local randomization and device imprecisions. Phys. Rev. A 90, 022306, 2014.
[11] A. Acin, D. Cavalcanti, E. Passaro, S. Pironio, P. Skrzypczyk. Necessary detection eciencies for secure quantum key distribution and bound randomness. Physical Review A 93, 012319 (2016)
[12] N. Aharon, S. Massar, S. Pironio, J. Silman. Device-Independent Bit Commitment based on the CHSH Inequality. New Journal of Physics 18 025014 (2016).
[13] L. Phuc Thinh, G. de la Torre, J.-D. Bancal, S. Pironio, V. Scarani. Randomness in post-selected events. New Journal of Physics 18 035007 (2016).
[14] E.Woodhead, S. Pironio. Secrecy in prepare-and-measure CHSH tests with a qubit bound. Physical Review Letters 115, 150501 (2015).
[15] M. Banik, S. Bhattacharya, A. Mukherjee, A. Roy, A. Ambainis, and A. Rai. Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound. Physical Review A, 92: 030103(R) (2015).
[16] H. Buhrman, . Czekaj, A. Grudka, M. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, and S. Strelchuk. Quantum communication complexity advantage implies violation of a Bell inequality. Proceedings of the National Academy of Sciences of the United States of America, vol. 113 no. 12 (2016).
Quantum game theory
[1] D. Kravchenko. A new quantization scheme for classical games. ICALP'2013 workshop on Quantum and Classical Complexity, pp.17-34.
[2] A. Pappa, P. Jouguet, T. Lawson, A. Chailloux, M. Legre, P. Trinkler, I. Kerenidis, E. Diamanti. Experimental plug and play quantum coin flipping, Nature Communications, 5,:3717
[3] A. Pappa, N. Kumar, T. Lawson, M. Santha, S. Zhang, E. Diamanti and I. Kerenidis. Nonlocality and conflicting interest games. Phys. Rev. Lett. 114, 020401, 2015
[4] D. Kravchenko. Quantum Entanglement in a Zero-Sum Game. Contributions to Game Theory and Management, 8 (to appear), 2015 Other publications [1] T. Cubitt, D. Elkouss, W. Matthews, M. Ozols, D. Perez-Garcia, S. Strelchuk. Unbounded number of channel uses may be required to detect quantum capacity. Nat. Commun. 6:6739 (2015). arXiv:1408.5115.
[2] K. Audenaert, N. Datta, M. Ozols. Entropy power inequalities for qudits. arXiv:1503.04213.
[3] S. Massar, S. Pironio, D. Pitalua-Garca. Hyperdense coding and superadditivity of classical capacities in hypersphere theories. New Journal of Physics 17 (11), 113002 (2015). arXiv:1504.05147.
[4] A. Kent, S. Massar, and J. Silman. Secure and Robust Transmission and Veri cation of Unknown Quantum States in Minkowski Space. Scienti c Reports 4, 3901 (2014).
Quantum information in computer science and physical systems
[1] S. Fiorini, S. Massar, M. K. Patra, and H. R. Tiwary. Generalised probabilistic theories and conic extensions of polytopes. J. Phys. A : Math. Theor. 48, 025302, 2015. arXiv:1310.4125.
[2] S. Massar and M. K. Patra. Information and communication in polygon theories. arXiv:1403.2509.
[3] D. Aharonov, I. Arad, and T. Vidick. The Quantum PCP Conjecture. ACM SIGACT News, 44, Issue 2, pp. 47--79, June 2013.
[4] M. Ben-Or and L. Eldar. Optimal Algorithms for Linear Algebra by Quantum Inspiration.arXiv:1312.3717.
[5] A. Ambainis and R. de Wolf. How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Computational Complexity, 23(2):305-322, 2014.
[6] U. Mahadev, R. de Wolf. Rational approximations and quantum algorithms with postselection. In Quantum Information and Computation, 15(3 & 4):295-307, 2014. arXiv:1401.0912.
[7] J. Kaniewski, T. Lee, R. de Wolf. Query complexity in expectation. Proceedings of 42nd Interna-tional Colloquium on Automata, Languages and Programming (ICALP 15), LNCS 9134, pp.761-772. arXiv:1411.7280.
[8] T. Lee, Z. Wei, R. de Wolf. Some upper and lower bounds on PSD-rank. arXiv:1407.4308
[9] N. de Beaudrap. On computation with 'probabilities' modulo k. arXiv:1405.7381
[10] M. Ben-Or, L. Eldar. Optimal algorithms for linear algebra by quantum inspiration. arXiv:1312.3717.
[11] T. Lee, A. Prakash, H. Yuen, R. de Wolf. On the sum-of-squares degree of symmetric quadratic functions. Proceedings of Computational Complexity Conference (CCC'16), to appear. arXiv:1601.02311
[12] S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, R. de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM (JACM) 62 (2), 17 (2015).
Quantum and classical complexity of fermionic systems
[1] N. Breuckmann, B.M. Terhal. Space-Time Circuit-to-Hamiltonian Construction and Its Applications. Journal of Physics A, 47:195304, 2014.
[2] D. Gosset, B. Terhal, A. Vershnyina, Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction, Phys. Rev. Lett. 114, 140501 (2015), arXiv:1409.7745
[3] A. Vershynina, Complete criterion for convex-Gaussian state detection, Phys. Rev. A 90, 062329 (2014), arXiv:1409.8480.
[4] A. Vershynina, Entanglement rates for bipartite open systems, Physical Review A 92, 022311 (2015). arXiv.org: 1505.00416
[5] S. Lloyd and B.M. Terhal. Adiabatic and Hamiltonian computing on a 2D lattice with simple two-qubit interactions. New Journal of Physics Vol. 18, 023042 (2016).
Preparing ground states of physical systems on a quantum computer
[1] S. Yang, L. Lehman, D. Poilblanc, K. Van Acoleyen, F. Verstraete, I. Cirac, N. Schuch. Edge theories in Projected Entangled Pair State models. Physical Review Letters, 112:036402, 2014.
[2] A. Ambainis. On physical problems that are slightly more difficult than QMA. IEEE Conference on Computational Complexity, 2014, to appear.
[3] N. de Beaudrap. Difficult instances of the counting problem for 2-quantum-SAT are very atypical. Proceeedings of TQC'14, 2014. arXiv:1403.1588
[4] A. Molnar, N. Schuch, F. Verstraete, J.I. Cirac. Approximating Gibbs states of local Hamiltonians eciently with PEPS. Phys. Rev. B 91, 045138 (2015); arXiv:1406.2973.
[5] M.B. Sahinoglu, D. Williamson, N. Bultinck, M. Marien, J. Haegeman, N. Schuch, F. Verstraete. Characterizing Topological Order with Matrix Product Operators. arXiv:1409.2150 (2014).
[6] S. Yang, T.B. Wahl, H. Tu, N. Schuch, J.I. Cirac. Chiral projected entangled-pair state with topological order. Phys. Rev. Lett. 114, 106803 (2015); arXiv:1411.6618.