Malvika Raj Joshi

Download CV malvika [at] berkeley [dot] edu Publications
Malvika Raj Joshi

I am a Ph.D. student in Computer Science at the University of California, Berkeley, where I am fortunate to be co-advised by Umesh Vazirani and John Wright. I am drawn to foundational questions about physics and computation, and I enjoy connecting the insights I learn from these questions to real-world applications in cryptography and privacy.

My primary research area is quantum complexity theory, specifically understanding the power of shallow quantum circuits (QAC0). These circuits are particularly relevant in the current NISQ era, where quantum devices are noisy and limited to constant depth. The question that keeps me up at night is whether QAC0 can implement the FANOUT operation (Parity ∈ QAC0?). The answer determines the power of QAC0 relative to classical circuit classes, from AC0 to TC0, as well as its ability to perform inherently quantum tasks such as preparing highly entangled states and the Quantum Fourier Transform.

Before starting my Ph.D. at Berkeley, I completed my Master's at Massachusetts Institute of Technology (MIT), where I was advised by Aram Harrow.
Thesis: Pretending to be Quantum: A Study of IQP-Based Tests of Quantumness.

Outside of research, I enjoy windsurfing at the Berkeley Marina and learning to play the drums.

Publications

  • Parity ∉ QAC0 ⟺ QAC0 is Fourier-Concentrated
    Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi.
    In 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2026.
    arXiv
    BibTeX 
    @misc{gretta2026paritynotinqac0iff,
      title={Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated}, 
      author={Lucas Gretta and Meghal Gupta and Malvika Raj Joshi},
      year={2026},
      eprint={2604.02793},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2604.02793}, 
}
  • Super-Constant Weight Dicke States in Constant Depth Without Fanout
    Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi.
    2026.
    arXiv
    BibTeX 
    @misc{gretta2026superconstantweightdickestates,
      title={Super-Constant Weight Dicke States in Constant Depth Without Fanout}, 
      author={Lucas Gretta and Meghal Gupta and Malvika Raj Joshi},
      year={2026},
      eprint={2604.15298},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2604.15298}, 
}
  • Improved Lower Bounds for QAC0
    Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright.
    In 58th Annual ACM Symposium on Theory of Computing (STOC), 2026.
    Proceedings arXiv Slides Video
    BibTeX 
    @inproceedings{joshi2026improvedlowerboundsqac0,
author = {Joshi, Malvika Raj and Tal, Avishay and Vasconcelos, Francisca and Wright, John},
title = {Improved Lower Bounds for QAC0},
year = {2026},
isbn = {9798400725364},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3798129.3800922},
doi = {10.1145/3798129.3800922},
booktitle = {Proceedings of the 58th Annual ACM Symposium on Theory of Computing},
pages = {2199–2209},
numpages = {11},
keywords = {QAC0, analysis of Boolean functions, quantum circuit complexity},
location = {Salt Lake City, UT, USA},
series = {STOC '26}
}
  • Constant-Depth Unitary Preparation of Dicke States
    Malvika Raj Joshi and Francisca Vasconcelos.
    2026.
    arXiv
    BibTeX 
    @misc{joshi2026constantdepthunitarypreparationdicke,
      title={Constant-Depth Unitary Preparation of Dicke States}, 
      author={Malvika Raj Joshi and Francisca Vasconcelos},
      year={2026},
      eprint={2601.10693},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2601.10693}, 
}
  • Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity
    Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams.
    In 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022.
    Proceedings ECCC
    BibTeX 
    @InProceedings{akmal_et_al:LIPIcs.ITCS.2022.3,
  author =	{Akmal, Shyan and Chen, Lijie and Jin, Ce and Raj, Malvika and Williams, Ryan},
  title =	{{Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{3:1--3:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.3},
  URN =		{urn:nbn:de:0030-drops-155991},
  doi =		{10.4230/LIPIcs.ITCS.2022.3},
  annote =	{Keywords: Fine-grained complexity, Merlin-Arthur proofs}
}

Selected Projects

  • Applied Scientist Intern, Amazon
    East Palo Alto, May–Aug. 2025.
    Designed Lexicure, a leakage-free encrypted lexical search protocol with improved communication tradeoffs and new secure primitives for higher-degree arithmetic.
    With Tal Wagner, Shai Halevi and Nina Mishra. Manuscript under submission.
  • Open Source Software Development Intern, PyTorch
    Facebook, New York, May–Aug. 2019.
    Designed and implemented a C++ API for PyTorch Autograd, introducing native C++ support for automatic differentiation.
    PyTorch contributions

For additional research, software engineering, outreach, and teaching experience, see my CV.