Anurag Anshu

According to our database, Anurag Anshu authored at least 52 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Learning shallow quantum circuits.

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, Jarrod R. McClean

CoRR, 2024

2023

One-Shot Quantum State Redistribution and Quantum Markov Chains.

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

IEEE Trans. Inf. Theory, September, 2023

Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations.

Anurag Anshu, Tony Metger

Quantum, May, 2023

Circuit-to-Hamiltonian from tensor networks and fault tolerance.

Anurag Anshu, Nikolas P. Breuckmann, Quynh T. Nguyen

CoRR, 2023

Fermionic Hamiltonians without trivial low-energy states.

Yaroslav Herasymenko, Anurag Anshu, Barbara M. Terhal, Jonas Helsen

CoRR, 2023

A survey on the complexity of learning quantum states.

Anurag Anshu, Srinivasan Arunachalam

CoRR, 2023

NLTS Hamiltonians from Good Quantum Codes.

Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Incompressibility of Classical Distributions.

Anurag Anshu, Debbie W. Leung, Dave Touchette

IEEE Trans. Inf. Theory, 2022

Distributed Quantum inner product estimation.

Anurag Anshu, Zeph Landau, Yunchao Liu

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

An area law for 2d frustration-free spin systems.

Anurag Anshu, Itai Arad, David Gosset

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians.

Anurag Anshu, Chinmay Nirkhe

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Improved approximation algorithms for bounded-degree local Hamiltonians.

Anurag Anshu, David Gosset, Karen J. Morenz Korol, Mehdi Soleimanifar

CoRR, 2021

On Query-To-Communication Lifting for Adversary Bounds.

Anurag Anshu, Shalev Ben-David, Srijita Kundu

Proceedings of the 36th Computational Complexity Conference, 2021

2020

One-Shot Capacity Bounds on the Simultaneous Transmission of Classical and Quantum Information.

Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, Rahul Jain, Javier Rodríguez Fonollosa

IEEE Trans. Inf. Theory, 2020

On the Compression of Messages in the Multi-Party Setting.

Anurag Anshu, Penghui Yao

IEEE Trans. Inf. Theory, 2020

Secure Communication Over Fully Quantum Gel'fand-Pinsker Wiretap Channel.

Anurag Anshu, Masahito Hayashi, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2020

Noisy Quantum State Redistribution With Promise and the Alpha-Bit.

Anurag Anshu, Min-Hsiu Hsieh, Rahul Jain

IEEE Trans. Inf. Theory, 2020

Partially Smoothed Information Measures.

Anurag Anshu, Mario Berta, Rahul Jain, Marco Tomamichel

IEEE Trans. Inf. Theory, 2020

Contextuality in multipartite pseudo-telepathy graph games.

Anurag Anshu, Peter Høyer, Mehdi Mhalla, Simon Perdrix

J. Comput. Syst. Sci., 2020

From communication complexity to an entanglement spread area law in the ground state of gapped local Hamiltonians.

Anurag Anshu, Aram W. Harrow, Mehdi Soleimanifar

CoRR, 2020

Beyond Product State Approximations for a Quantum Analogue of Max Cut.

Anurag Anshu, David Gosset, Karen Morenz

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Entanglement subvolume law for 2d frustration-free spin systems.

Anurag Anshu, Itai Arad, David Gosset

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Sample-efficient learning of quantum many-body systems.

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2019

A Hypothesis Testing Approach for Communication Over Entanglement-Assisted Compound Quantum Channel.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2019

Building Blocks for Communication Over Noisy Quantum Networks.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2019

Second-Order Characterizations via Partial Smoothing.

Anurag Anshu, Mario Berta, Rahul Jain, Marco Tomamichel

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

A Generalized Quantum Slepian-Wolf.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2018

A One-Shot Achievability Result for Quantum State Redistribution.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

IEEE Trans. Inf. Theory, 2018

Expected Communication Cost of Distributed Quantum Tasks.

Anurag Anshu, Ankit Garg, Aram W. Harrow, Penghui Yao

IEEE Trans. Inf. Theory, 2018

Quantum Log-Approximate-Rank Conjecture is also False.

Anurag Anshu, Naresh Goud Boddu, Dave Touchette

Electron. Colloquium Comput. Complex., 2018

One-shot Capacity Bounds on the Simultaneous Transmission of Public and Private Information Over Quantum Channels.

Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, Rahul Jain, Javier R. Fonollosa

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Building Blocks for Communication Over Noisy Quantum Nerworks.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

2017

Lifting randomized query complexity to randomized communication complexity.

Anurag Anshu, Naresh B. Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

Electron. Colloquium Comput. Complex., 2017

A Composition Theorem for Randomized Query complexity.

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2017

Measurement compression with quantum side information using shared randomness.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

CoRR, 2017

A unified approach to source and message compression.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

CoRR, 2017

One shot entanglement assisted classical and quantum communication over noisy quantum channels: A hypothesis testing and convex split approach.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

CoRR, 2017

Smooth min-max relative entropy based bounds for one-shot classical and quantum state redistribution.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

CoRR, 2017

On the rectilinear crossing number of complete uniform hypergraphs.

Anurag Anshu, Rahul Gangopadhyay, Saswata Shannigrahi, Satyanarayana Vusirikala

Comput. Geom., 2017

Exponential separation of quantum communication and classical information.

Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

An upper bound on quantum capacity of unital quantum channels.

Anurag Anshu

Proceedings of the 2017 IEEE Information Theory Workshop, 2017

Achievability bounds on quantum state redistribution using convex split and position based decoding.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

Proceedings of the 2017 IEEE Information Theory Workshop, 2017

Separating Quantum Communication and Approximate Rank.

Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Teleportation of Quantum States.

Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain, Priyanka Mukhopadhyay

Encyclopedia of Algorithms, 2016

New One Shot Quantum Protocols With Application to Communication Complexity.

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

IEEE Trans. Inf. Theory, 2016

Separations in communication complexity using cheat sheets and information complexity.

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Electron. Colloquium Comput. Complex., 2016

A lower bound on the crossing number of uniform hypergraphs.

Anurag Anshu, Saswata Shannigrahi

Discret. Appl. Math., 2016

Lower Bound on Expected Communication Cost of Quantum Huffman Coding.

Anurag Anshu, Ankit Garg, Aram W. Harrow, Penghui Yao

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

2014

A new operational interpretation of relative entropy and trace distance between quantum states.

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

CoRR, 2014

Near optimal bounds on quantum communication complexity of single-shot quantum state redistribution.

Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain

CoRR, 2014

2013

Pseudo-telepathy games and genuine ns k-way nonlocality using graph states.

Anurag Anshu, Mehdi Mhalla

Quantum Inf. Comput., 2013