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 algorithms for classical computers to perform calculations that were previously deemed only possible with quantum computers. That research began under the supervision of Scott Aaronson when Tang was only a teenager.
Ewin Tang | |
|---|---|
| Born | 2000 (age 23–24) |
| Alma mater | University of Texas at Austin |
| Scientific career | |
| Fields | Computer science, Quantum Information |
| Doctoral advisor | James Lee |
| Other academic advisors | Scott Aaronson |
| Website | https://ewintang.com/ |
Early life
editTang skipped the fourth, fifth, and sixth grades in order to enroll at the University of Texas at Austin at the age of 14.[2] Tang's first experience of research involved working on in vivo imaging for biomedical research such as optical probes to view polarised 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.[3] In 2017 she took a class on quantum information taught by Scott Aaronson, who would soon become her dissertation 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.[2]
Research
editBefore Tang's work, the best known classical algorithms solving some linear algebra problems were exponentially slower, under some assumptions, than the best quantum algorithm for the same problem. Inspired by the quantum solution, 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.
Her first work in quantum computing was her 2018 thesis dissertation titled A quantum-inspired classical algorithm for recommendation systems,[pub 5] supervised by Scott Aaronson, allowing her to complete two undergraduate degrees in computer science and in pure mathematics from the UT Austin. This work details a new algorithm that solves the recommendation problem; for example, how does Amazon or Netflix predict which books or movies a specific consumer will personally enjoy? A linear algebraic approach of the problem is the following: given m users, and n products, alongside incomplete data about which products the users prefer (organised in a binary tree data structure) where there are not too many ways the users can vary their preferences (called low-rank matrices), what are the products that a given user may want to buy? A common linear algebraic classical strategy to solve this problem is to reconstruct an approximation of the full preference matrix and use it to predict the next preferred product. Such a strategy uses at least a time polynomial in the matrix dimension.
In 2016, Iordanis Kerenidis and Anupam Prakash, found an exponentially faster quantum algorithm;[4] this algorithm uses the HHL algorithm to sample the product directly from an approximation of the preference matrix without reconstructing the matrix itself, thus avoiding the polynomial limit mentioned above. Tang's classical algorithm, inspired by the fast quantum algorithm of Kerenidis and Prakash, is able to perform the same calculations but on a normal computer without the need for quantum machine learning. Both approaches run in polylogarithmic time which means the total computation time scales with the logarithm of the problem variables such as the total number of products and users, except Tang utilises a classical replication 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. As he said, "that seemed to me like an important 't' to cross to complete this story".[2] Before Tang's research was made public, she and Aaronson attended a quantum computing workshop at the University of California where Tang presented in front of an audience that included Kerenidis and Prakash on June 18 and 19 2018.[5] After four hours of questioning, the consensus was that Tang's classical algorithm seemed correct. The recommendation problem was one of a handful of projects offered by Aaronson, which was chosen reluctantly by Tang: "I was hesitant because it seemed like a hard problem when I looked at it, but it was the easiest of the problems he gave me".[2]
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.[6]
In the same year, Tang began her Ph.D. in theoretical computer science at the University of Washington under the supervision of James Lee.[2] She pursued her research and generalized the above result, dequantizing other quantum machine learning HHL-based problems: principal component analysis[pub 6] and low-rank stochastic regression.[pub 7]
Media coverage
editThere was wide media coverage in response to Tang's work on using classical computing rather than quantum computing to tackle the recommendation problem, due to the perception that it eliminates one of the best examples of quantum speedup.[2][7][8][9] Some researchers came to the defence of quantum computing, such as Robert Young (Director of the University of Lancaster's Quantum Technology Centre), who said in a BBC news article, "If we hadn't invested in quantum computing, the quantum algorithm that inspired [Ms] Tang wouldn't have existed".[8] Tang herself notes 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".[2]
At the age of 18, Tang was named as one of Forbes 30 Under 30 for 2019 due to her work in developing computing methods that allow classical computers to handle tasks previously deemed only possible with a quantum computer.[10]
Selected publications
edit- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ a b 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.
- ^ a b 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.
- ^ a b 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
edit- ^ Knapp, Alex, ed. (2018). "The 2019 30 under 30 Inventing the future from the atom up - Science". Forbes.
- ^ a b c d e f g "Teenager Finds Classical Alternative to Quantum Recommendation Algorithm | Quanta Magazine". Quanta Magazine. Retrieved 2018-11-14.
- ^ "Davidson Fellows 2014". www.davidsongifted.org. Retrieved 2018-11-14.
- ^ Kerenidis, Iordanis; Prakash, Anupam (2016-03-29). "Quantum Recommendation Systems". arXiv:1603.08675 [quant-ph].
- ^ "Challenges in Quantum Computation | Simons Institute for the Theory of Computing". simons.berkeley.edu. 9 January 2018. Retrieved 2018-11-14.
- ^ "Graduating Natural Sciences Students Make Their Mark at UT Austin". Retrieved 2018-11-14.
- ^ "A Student Took Down One of Quantum Computing's Top Applications—Now What?". Singularity Hub. 2018-08-12. Retrieved 2018-11-14.
- ^ a b Russon, Mary-Ann (2018-09-04). "The race to make the world's most powerful computer ever". BBC News. Retrieved 2018-11-14.
- ^ "Maybe We Don't Need Quantum Computing After All - Developer.com". www.developer.com. 7 August 2018. Retrieved 2018-11-14.
- ^ "Ewin Tang". Forbes. Retrieved 2018-11-14.