Ashwin Nayak:    Publications

These works are copyrighted, and the copyright is held by the authors and/or the publishers (e.g., ACM, IEEE, Springer). They are provided only for academic use.


Manuscripts

  1. Shima Bab Hadiashar, Ashwin Nayak, and Pulkit Sinha.

  2. Optimal lower bounds for Quantum Learning via Information Theory.    [ pdf ]     [ bib ]     [ link ]

  3. Preprint arXiv:2301.02227 [quant-ph], 2023.


  1. Angus Lowe and Ashwin Nayak.

  2. Lower Bounds for Learning Quantum States with Single-Copy Measurements.    [ pdf ]     [ bib ]     [ link ]

  3. Preprint arXiv:2207.14438 [quant-ph], 2022.


  1. Ashwin Nayak and and Henry Yuen.

  2. Rigidity of Superdense Coding.    [ pdf ]     [ bib ]     [ link ]

  3. Preprint arXiv:2012.01672 [quant-ph], 2020. Last revised Apr. 2023.

  4. To appear in ACM Transactions on Quantum Computing.


  1. Ashwin Nayak, Leonard J. Schulman, Umesh V. Vazirani.

  2. A Quantum Algorithm for the Ferromagnetic Ising Model.    [ pdf ]

  3. Manuscript, 2008.


  1. Rahul Jain and Ashwin Nayak.

  2. Accessible versus Holevo Information for a Binary Random Variable.    [ pdf ]

  3. Preprint quant-ph/0603278, Mar. 2006. Revised Sept. 2007.


  1. Ashwin Nayak and Ashvin Vishwanath.

  2. Quantum Walk on the Line.   [ pdf ]

  3. Preprint quant-ph/0010117, Oct. 2000.

  4. Some of the results in this paper were reported in STOC'01.



Refereed publications

  1. Máté Farkas, Jędrzej Kaniewski, and Ashwin Nayak.

  2. Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding.    [ pdf ]     [ bib ]     [ link ]

  3. IEEE Transactions on Information Theory, 69(6):3814–3824, 2023.


  1. Ashwin Nayak.

  2. Deterministic Algorithms for the Hidden Subgroup Problem.    [ pdf ]     [ bib ]     [ link ]

  3. Quantum Information and Computation, 22(9&10):755–769, 2022.


  1. Frédéric Magniez and Ashwin Nayak.

  2. Quantum Distributed Complexity of Set Disjointness on a Line.    [ pdf ]     [ bib ]     [ link ]

  3. ACM Transactions on Computation Theory, 14(1), article 5:1–22, 2022.

  4. Improves over earlier version in Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), 82:1–82:18, 2020.     [ bib ]     [ link ]


  1. Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, and Dave Touchette.

  2. One-Shot Quantum State Redistribution and Quantum Markov Chains.    [ pdf ]

  3. Extended abstract appeared in Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 130–135, 2021.     [ pdf ]     [ bib ]     [ link ]

  4. To appear in IEEE Transactions on Information Theory.


  1. Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu.

  2. Capacity Approaching Coding for Low Noise Interactive Quantum Communication. Part I: Large Alphabets.        [ pdf ]    [ bib ]    [ link ]

  3. IEEE Transactions on Information Theory, 67(8):5443–5490, 2021. 

  4. Extended abstract in Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, pages 339–352, 2018.    [ pdf ]    [ bib ]    [ link ]



  1. Shima Bab Hadiashar and Ashwin Nayak.

  2. On the Entanglement Cost of One-Shot Compression.    [ pdf ]     [ bib ]     [ link ]

  3. Quantum, 4:286, June 2020.


  1. Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak.

  2. Online Learning of Quantum States.    [ pdf ]     [ bib ]     [ link ]

  3. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124019, 2019.

  4. Invited article, Special issue on Machine Learning.

  5. Conference version in Advances in Neural Information Processing Systems 31, pages 8976–8986, 2018. (Proceedings of the 32nd Conference on Neural Information Processing Systems.)     [ pdf ]     [ bib ]      [ link ]


  1. Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, and Falk Unger.

  2. Noisy Interactive Quantum Communication.    [ pdf ]     [ bib ]     [ link ]

  3. SIAM Journal on Computing, 48(4):1147–1195, 2019.

  4. Extended abstract appeared in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 296–305, 2014.    [ pdf ]    [ bib ]    [ link ]


  1. Shima Bab Hadiashar, Ashwin Nayak, and Renato Renner.

  2. Communication Complexity of One-Shot Remote State Preparation.    [ pdf ]     [ bib ]     [ link ]

  3. IEEE Transactions on Information Theory, 64(7):4709–4728, 2018.


  1. Ashwin Nayak and Dave Touchette.

  2. Augmented Index and Quantum Streaming Algorithms for DYCK(2).    [ pdf ]

  3. Extended abstract in Proceedings of the 32nd Computational Complexity Conference, Leibniz International Proceedings in Informatics, Vol. 79, pages 23:1–23:21, 2017.    [ bib ]    [ link ]


  1. Ashwin Nayak, Jamie Sikora, and Levent Tuncel.

  2. A Search for Quantum Coin-Flipping Protocols Using Optimization Techniques.    [ pdf ]     [ bib ]     [ link ]

  3. Mathematical Programming (Series A), 156(1):581–613, 2016. Supplementary material 49 pages.


  1. Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, and David Xiao.

  2. Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority.    [ pdf ]    [ bib ]    [ link ]

  3. Random Structures & Algorithms, 48(3):612–638, 2016.

  4. This work presents an improvement of the results reported by a subset of the authors in ICALP 2011:

  5. Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao.
    Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority.   [ pdf ]    [ bib ]    [ link ]
    In Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6755, pages 317–329, 2011.


  1. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak.
    Recognizing Well-Parenthesized Expressions in the Streaming Model.    [ pdf ]    [ bib ]    [ link ]

  2. SIAM Journal on Computing, 43(6):1880–1905, 2014.

  3. Preliminary version in Proceedings of the Forty-second Annual ACM Symposium on the Theory of Computing, pages 261–270, 2010.      [ pdf ]   [ bib ]    [ link ]


  1. Rahul Jain and Ashwin Nayak.

  2. The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: the Index Function Revisited.  [ pdf ]   [ bib ]    [ link ]    [ talk (see application III), talk ]

  3. IEEE Transactions on Information Theory, 60(10):6646–6668, 2014.


  1. Rahul Jain and Ashwin Nayak.

  2. Short Proofs of the Quantum Substate Theorem.   [ pdf ]   [ bib ]    [ link ]    [ talk ]

  3. IEEE Transactions on Information Theory 58(6):3664–3669, 2012.


  1. Frédéric Magniez, Ashwin Nayak, Peter Richter, and Miklos Santha.

  2. On the Hitting Times of Quantum Versus Random Walks.   [ pdf ]   [ bib ]    [ link ]

  3. Algorithmica 63(1):91–116, 2012.

  4. Preliminary version in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 86–95, 2009.       [ pdf ]   [ bib ]


  1. Ashwin Nayak.

  2. Inverting a Permutation is as Hard as Unordered Search.   [ pdf ]   [ bib ]   [ link ]

  3. Theory of Computing 7(1):19–25, 2011.


  1. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha.

  2. Search via Quantum Walk.    [ pdf ]   [ bib ]   [ link ]

  3. SIAM Journal on Computing, 40(1):142–164, 2011.

  4. Earlier version in Proceedings of the Thirty-Ninth Annual ACM Symposium on the Theory of Computing, pages 575–584, 2007.      [ pdf ]    [ talk ]


  1. Rahul Jain, Ashwin Nayak, and Yi Su.

  2. A Separation between Divergence and Holevo Information for Ensembles.   [ pdf ]   [ bib ]

  3. Mathematical Structures in Computer Science, 20(5):977–993, 2010. Special issue devoted to selected articles from Theory and Applications of Models of Computation (TAMC 2008, 2009).

  4. Preliminary version in Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science, Vol. 4978, pages 526–541, 2008.      [ pdf ]   [ bib ]


  1. Tzu-Chieh Wei, Michele Mosca, and Ashwin Nayak.

  2. Interacting Boson Problems can be QMA-hard.   [ pdf ]   [ bib ]

  3. Physical Review Letters, 104(040501), 2010.


  1. Rahul Jain, Hartmut Klauck, and Ashwin Nayak.

  2. Direct Product Theorems for Communication Complexity via Subdistribution Bounds.   [ pdf ]   [ bib ]

  3. In Proceedings of the Fortieth Annual ACM Symposium on the Theory of Computing, pages 599–608, 2008.


  1. Frédéric Magniez and Ashwin Nayak.

  2. Quantum Complexity of Testing Group Commutativity.   [ pdf ]

  3. Algorithmica, 48(3), pages 221–232, 2007.

  4. Earlier version in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 1770, pages 1312–1324, 2005.       [ pdf ]


  1. Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman.

  2. Interaction in Quantum Communication.    [ pdf ]

  3. IEEE Transactions on Information Theory, 53(6), pages 1970–1982, Jun. 2007.

  4. This article presents several improvements of the techniques and results in the conference article:

  5. Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman.

  6. Interaction in Quantum Communication and the Complexity of Set Disjointness.   [ pdf ]

  7. In Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing, pages 124–133, 2001.


  1. Ashwin Nayak and Pranab Sen.

  2. Invertible Quantum Operations and Perfect Encryption of Quantum States.    [ pdf ]

  3. Quantum Information and Computation, 7(1), pages 103–110, Jan. 2007.


  1. Paul Dickinson and Ashwin Nayak.

  2. Approximate Randomization of Quantum States with Fewer Bits of Key.   [ pdf ]

  3. Invited paper, Quantum Computing Back Action, IIT Kanpur, India, March 6–12, 2006.

  4. AIP Conference Proceedings (refereed volume), Vol. 864, pages 18–36, 2006.


  1. Ashwin Nayak and Julia Salzman.

  2. Limits on the Ability of Quantum States to Convey Classical Messages.     [ pdf ]

  3. Journal of the ACM, 53(1), pages 184–206, 2006.

  4. This consolidates results from two conference articles:

  5. Ashwin Nayak.

  6. Optimal Lower Bounds for Quantum Automata and Random Access Codes.   [ pdf ]

  7. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 369–376, 1999.


  9. Ashwin Nayak and Julia Salzman.

  10. On Communication Over an Entanglement-Assisted Quantum Channel.   [ pdf ]

  11. In Proceedings of the Thirty-Fourth Annual ACM Symposium on the Theory of Computing, pages 698–704, 2002.

  12. In the joint session with the 17th Annual IEEE Conference on Computational Complexity, 2002.


  1. Jonathan Baugh, Osama Moussa, Colm Ryan, Ashwin Nayak, and Raymond Laflamme.

  2. Experimental Implementation of Heat-Bath Algorithmic Cooling Using Solid-State Nuclear Magnetic Resonance.     [ pdf ]

  3. Nature, 438, pages 470–473, 2005.


  1. Iordanis Kerenidis and Ashwin Nayak.

  2. Weak Coin Flipping with Small Bias.   [ pdf ]

  3. Information Processing Letters, 89(3), pages 131–135, 2004.


  1. Ashwin Nayak and Peter Shor.

  2. Bit-Commitment-Based Quantum Coin Flipping.   [ pdf ]

  3. Physical Review A, 67, article no. 012304, 2003.


  1. Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani.

  2. Dense Quantum Coding and Quantum Finite Automata.   [ pdf ]

  3. Journal of the ACM, 49(4), pages 1–16, 2002.

  4. This consolidates some results from two conference articles:

  5. Ashwin Nayak.

  6. Optimal Lower Bounds for Quantum Automata and Random Access Codes.   [ pdf ]

  7. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 369–376, 1999.


  9. Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani.

  10. Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.   [ pdf ]

  11. In Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, pages 376–383, 1999.


  1. Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous.

  2. One-Dimensional Quantum Walks.   [ pdf ]

  3. In Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing, pages 37–49, 2001.

  4. This paper reports some of the results in an earlier manuscript: quant-ph/0010117.


  1. Ashwin Nayak and Felix Wu.

  2. The Quantum Query Complexity of Approximating the Median and Related Statistics.   [ pdf ]

  3. In Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, pages 384–393, 1999.

  4. Optimal algorithms for some approximate statistics appear in my PhD thesis, 1999.


  1. Ashwin Nayak, Alistair Sinclair, and Uri Zwick.

  2. Spatial Codes and the Hardness of String Folding Problems.   [ pdf ]

  3. Journal of Computational Biology, 6(1), pages 13–36, 1999.

  4. Preliminary version in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 639–648, 1998.     [ pdf ]



Miscellaneous

  1. Ashwin Nayak, Peter Richter, and Mario Szegedy.

  2. Quantum Analogues of Markov Chains.    [ pdf ]

  3. Encyclopedia of Algorithms, Springer Berlin Heidelberg, 2015.


  1. Robin Kothari and Ashwin Nayak.

  2. Quantum Algorithms for Matrix Multiplication and Product Verification.    [ pdf ]

  3. Encyclopedia of Algorithms, Springer Berlin Heidelberg, 2015.


  1. Ashwin Nayak.

  2. Checking Matrix Identities.   [ pdf ]   [ errata ]

  3. Encyclopedia of Algorithms, 2008.


  1. Todd Brun, Hartmut Klauck, Ashwin Nayak, Martin Rötteler, and Christof Zalka.

  2. Comment on ``Probabilistic Quantum Memories''.   [ pdf ]

  3. Physical Review Letters, 91(20), article no. 209801, 2003.



Thesis


  1. Ashwin Nayak.

  2. Lower Bounds for Quantum Computation and Communication.    [ pdf ]

  3. Ph.D. dissertation, Computer Science Division,

  4. University of California, Berkeley, December 1999.



Last updated June 19, 2022