Ewin Tang

Last updated
Ewin Tang
Born2000 (age 2425)
Alma mater University of Texas at Austin (BS)
University of Washington (PhD)
Awards Maryam Mirzakhani New Frontiers Prize (2025)
Scientific career
Fields Theoretical computer science
Quantum computing
Doctoral advisor James Lee
Other academic advisors Scott Aaronson
Website https://ewintang.com/

Ewin Tang (born 2000) is a computer scientist at the University of California, Berkeley. She was named as one of 2019 Science Forbes 30 Under 30 [1] for her work developing classical algorithms which matched the performance of the fastest known quantum algorithms, done as an undergraduate under the supervision of Scott Aaronson.

Contents

Early life

Tang skipped the fourth, fifth, and sixth grades to take courses at a local high school and at the University of Texas at Arlington at the age of 10, [2] [3] and then enrolled at the University of Texas at Austin at the age of 14. [4] Tang first began research working with her mother, Wen-Jing Hu, in the nanotechnology laboratory of her father, Liping Tang, [2] on in vivo imaging for biomedical research such as optical probes to view polarized macrophages during foreign body reactions, [pub 1] bacterial infection, [pub 2] fibrin deposition, [pub 3] and real-time detection of neutrophil responses. [pub 4]

In 2014 Tang was awarded an Davidson Fellow Honorable Mention for her work on an optical imaging probe for real-time detection of infection. [5] In 2017 she took a class on quantum information taught by Scott Aaronson, who became her undergraduate thesis adviser. Aaronson recognised Tang as an "unusually talented student" and presented her with a range of research projects to choose from; among them was the recommendation problem. [4]

Research

Tang's first work in quantum computing was her 2018 undergraduate thesis titled A quantum-inspired classical algorithm for recommendation systems, [pub 5] supervised by Scott Aaronson as a part of her undergraduate degree in computer science and in pure mathematics from UT Austin. The thesis gives a new algorithm that solves a matrix completion problem, motivated by applications to recommendation systems.

Before Tang's thesis, the best known classical algorithms for matrix completion were exponentially slower, under some assumptions, than the best quantum algorithm for the same problem. Inspired by the quantum algorithms, which were based on the HHL algorithm, she found [pub 5] [pub 6] [pub 7] classical algorithms solving these problem in a similar time as the quantum algorithms, under similar assumptions, thus "dequantizing" them and exponentially improving over the best known classical algorithms.

The best known quantum algorithm for matrix completion had been introduced in 2016 by Iordanis Kerenidis and Anupam Prakash, which runs exponentially faster, in polylogarithmic time, and uses the HHL algorithm as a subroutine. [6] Tang's algorithm also runs in polylogarithmic time, though Tang's algorithm uses a classical analog of the quantum sampling techniques. Prior to Tang's results, it was widely assumed that no fast classical algorithm existed; Kerenidis and Prakash did not attempt to study the classical solution, and the task assigned to Tang by Aaronson was to prove its nonexistence. Before the results were made public, Tang presented a preliminary version of the algorithm at a quantum computing workshop in June 2018 at the University of California, where the audience included Aaronson, Kerenidis, and Prakash. [7] After four hours of questioning, the consensus was that Tang's classical algorithm seemed correct. Tang published her results in STOC in June 2019, [pub 5] and in Physical Review Letters in August 2021. [pub 6]

In 2018 Tang was named as a University of Texas at Austin Dean's Honored Graduate in computer science, having maintained a 4.0 grade-point average. [8]

In 2023 Tang completed her Ph.D. in theoretical computer science at the University of Washington under the supervision of James Lee, [9] where she continued her undergraduate work on quantum-inspired classical algorithms for other problems, such as principal component analysis [pub 6] and low-rank stochastic regression. [pub 7]

Media coverage

There was wide media coverage in response to Tang's work on the recommendation problem, which was perceived as eliminating one of the best examples of quantum speedup. [4] [10] [11] [12] Some researchers defended quantum computing approaches, such as Robert Young, director of the Quantum Technology Centre at Lancaster University, who said "If we hadn't invested in quantum computing, the quantum algorithm that inspired [Ms] Tang wouldn't have existed." [11] Tang herself noted the divisive nature of comparing classical to quantum algorithms, and the trepidation of proving her algorithm to her adviser, "I started believing there is a fast classical algorithm, but I couldn’t really prove it to myself because Scott [Aaronson] seemed to think there wasn’t one, and he was the authority." [4]

In 2019, at the age of 18, Tang was named as one of Forbes 30 Under 30 for developing a computing method "allowing regular computers to solve a particular problem as quickly as a quantum computer." [13]

In 2025, she received a Maryam Mirzakhani New Frontiers Prize for "developing classical analogs of quantum algorithms for machine learning and linear algebra, and for advances in quantum machine learning on quantum data." [14] This prize is given to women mathematicians who completed their PhD's within the past two years. Each year, up to three of the prizes can be awarded.

Selected publications

  1. Baker, David W.; Zhou, Jun; Tsai, Yi-Ting; Patty, Kaitlen M.; Weng, Hong; Tang, Ewin N.; Nair, Ashwin; Hu, Wen-Jing; Tang, Liping (July 2014). "Development of optical probes for in vivo imaging of polarized macrophages during foreign body reactions". Acta Biomaterialia. 10 (7): 2945–2955. doi:10.1016/j.actbio.2014.04.001. ISSN   1742-7061. PMC   4041819 . PMID   24726956.
  2. Tang, Ewin N.; Nair, Ashwin; Baker, David W.; Hu, Wenjingin vi; Zhou, Jun (May 2014). "In Vivo Imaging of Infection Using a Bacteria-Targeting Optical Nanoprobe". Journal of Biomedical Nanotechnology. 10 (5): 856–863. doi:10.1166/jbn.2014.1852. ISSN   1550-7033. PMC   5033601 . PMID   24734538.
  3. Tsai, Yi-Ting; Zhou, Jun; Weng, Hong; Tang, Ewin N.; Baker, David W.; Tang, Liping (February 2014). "Optical imaging of fibrin deposition to elucidate participation of mast cells in foreign body responses". Biomaterials. 35 (7): 2089–2096. doi:10.1016/j.biomaterials.2013.11.040. ISSN   0142-9612. PMC   3934503 . PMID   24342726.
  4. Zhou, Jun; Tsai, Yi-Ting; Weng, Hong; Tang, Ewin N; Nair, Ashwin; Digant, Dave; Tang, Liping (May 2012). "Real-time detection of implant-associated neutrophil responses using a formyl peptide receptor-targeting NIR nanoprobe". International Journal of Nanomedicine. 7: 2057–68. doi: 10.2147/ijn.s29961 . ISSN   1178-2013. PMC   3356202 . PMID   22619542.
  5. 1 2 3 Tang, Ewin (2018-07-10). "A quantum-inspired classical algorithm for recommendation systems". Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. pp. 217–228. arXiv: 1807.04271 . doi:10.1145/3313276.3316310. ISBN   9781450367059. S2CID   44036160.
  6. 1 2 3 Tang, Ewin (2021). "Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions". Physical Review Letters. 127 (6): 060503. arXiv: 1811.00414 . Bibcode:2021PhRvL.127f0503T. doi:10.1103/PhysRevLett.127.060503. PMID   34420330. S2CID   236956378.
  7. 1 2 Gilyén, András; Lloyd, Seth; Tang, Ewin (2018-11-12). "Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimensions". arXiv: 1811.04909 [cs.DS].

References

  1. Knapp, Alex, ed. (2018). "The 2019 30 under 30 Inventing the future from the atom up - Science". Forbes.
  2. 1 2 "Cultivating Genius". uta.edu. 2018-04-03. Archived from the original on 2018-07-25.
  3. "Wayback Machine" (PDF). cie-dfw.org. p. 13. Archived from the original (PDF) on 2025-08-14.
  4. 1 2 3 4 "Teenager Finds Classical Alternative to Quantum Recommendation Algorithm | Quanta Magazine". Quanta Magazine. Retrieved 2018-11-14.
  5. "Davidson Fellows 2014". www.davidsongifted.org. Retrieved 2018-11-14.
  6. Kerenidis, Iordanis; Prakash, Anupam (2016-03-29). "Quantum Recommendation Systems". arXiv: 1603.08675 [quant-ph].
  7. "Challenges in Quantum Computation | Simons Institute for the Theory of Computing". simons.berkeley.edu. 9 January 2018. Retrieved 2018-11-14.
  8. "Graduating Natural Sciences Students Make Their Mark at UT Austin" . Retrieved 2018-11-14.
  9. Tang, Ewin (2023). Quantum Machine Learning Without Any Quantum (Ph.D. thesis).
  10. "A Student Took Down One of Quantum Computing's Top Applications—Now What?". Singularity Hub. 2018-08-12. Retrieved 2018-11-14.
  11. 1 2 Russon, Mary-Ann (2018-09-04). "The race to make the world's most powerful computer ever". BBC News. Retrieved 2018-11-14.
  12. "Maybe We Don't Need Quantum Computing After All - Developer.com". www.developer.com. 7 August 2018. Retrieved 2018-11-14.
  13. "Ewin Tang". Forbes. Retrieved 2018-11-14.
  14. https://breakthroughprize.org/Laureates/3/L3982