New Ideas for Quantum Algorithms
New applications for quantum walks
[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 Dierence 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 Congurations 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
Resources for 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 certification 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 verified 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 Certicate 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. Hyer, 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
Quantum communication complexity
[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 veriers. 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 certication 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 Verication of Unknown Quantum States in Minkowski Space. Scientic Reports 4, 3901 (2014).
Quantum information in computer science and physical systems
Applying quantum ideas to classical computer science
[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.