Ewin Tang

Last updated
Ewin Tang
Born2000 (age 22–23)
Alma mater University of Texas at Austin
Scientific career
Fields Computer science, Quantum Information
Doctoral advisor James Lee
Other academic advisorsScott Aaronson
Website https://ewintang.com/

Ewin Tang (born 2000) is a computer scientist at the University of Washington. 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.

Contents

Early life

Tang 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

Before 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

There 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

  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 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 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].

Related Research Articles

<span class="mw-page-title-main">BQP</span> Computational complexity class of problems

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem.

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that exploits quantum mechanical phenomena. At small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. In particular, a large-scale quantum computer could break widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is still largely experimental and impractical.

In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

Unconventional computing is computing by any of a wide range of new or unusual methods. It is also known as alternative computing.

A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.

Umesh Virkumar Vazirani is an Indian-American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.

In quantum computing, the threshold theorem states that a quantum computer with a physical error rate below a certain threshold can, through application of quantum error correction schemes, suppress the logical error rate to arbitrarily low levels. This shows that quantum computers can be made fault-tolerant, as an analogue to von Neumann's threshold theorem for classical computation. This result was proven by the groups of Dorit Aharanov and Michael Ben-Or; Emanuel Knill, Raymond Laflamme, and Wojciech Zurek; and Alexei Kitaev independently. These results built off a paper of Peter Shor, which proved a weaker version of the threshold theorem.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

The quantum algorithm for linear systems of equations, also called HHL algorithm, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm published in 2008 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

<span class="mw-page-title-main">Quantum machine learning</span> Interdisciplinary research area at the intersection of quantum physics and machine learning

Quantum machine learning is the integration of quantum algorithms within machine learning programs. The most common use of the term refers to machine learning algorithms for the analysis of classical data executed on a quantum computer, i.e. quantum-enhanced machine learning. While machine learning algorithms are used to compute immense quantities of data, quantum machine learning utilizes qubits and quantum operations or specialized quantum systems to improve computational speed and data storage done by algorithms in a program. This includes hybrid methods that involve both classical and quantum processing, where computationally difficult subroutines are outsourced to a quantum device. These routines can be more complex in nature and executed faster on a quantum computer. Furthermore, quantum algorithms can be used to analyze quantum states instead of classical data. Beyond quantum computing, the term "quantum machine learning" is also associated with classical machine learning methods applied to data generated from quantum experiments, such as learning the phase transitions of a quantum system or creating new quantum experiments. Quantum machine learning also extends to a branch of research that explores methodological and structural similarities between certain physical systems and learning systems, in particular neural networks. For example, some mathematical and numerical techniques from quantum physics are applicable to classical deep learning and vice versa. Furthermore, researchers investigate more abstract notions of learning theory with respect to quantum information, sometimes referred to as "quantum learning theory".

Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible usage of boson scattering to evaluate expectation values of permanents of matrices. The model consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement computing tasks which are hard to implement with classical computers by using far fewer physical resources than a full linear-optical quantum computing setup. This advantage makes it an ideal candidate for demonstrating the power of quantum computation in the near term.

The DiVincenzo criteria are conditions necessary for constructing a quantum computer, conditions proposed in 2000 by the theoretical physicist David P. DiVincenzo, as being those necessary to construct such a computer—a computer first proposed by mathematician Yuri Manin, in 1980, and physicist Richard Feynman, in 1982—as a means to efficiently simulate quantum systems, such as in solving the quantum many-body problem.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. The power of quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

In quantum computing, quantum supremacy, quantum primacy or quantum advantage is the goal of demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time. Conceptually, quantum supremacy involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has a superpolynomial speedup over the best known or possible classical algorithm for that task. The term was coined by John Preskill in 2012, but the concept of a qualitative quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's (1980) and Richard Feynman's (1981) proposals of quantum computing. Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, D-Wave's specialized frustrated cluster loop problems, and sampling the output of random quantum circuits.

Ronald Michiel de Wolf is a Dutch Computer Scientist, currently a Senior Researcher at Centrum Wiskunde & Informatica (CWI) and a professor at the Institute for Logic, Language and Computation (ILLC) of the University of Amsterdam (UvA).

Cross-entropy benchmarking is quantum benchmarking protocol which can be used to demonstrate quantum supremacy. In XEB, a random quantum circuit is executed on a quantum computer multiple times in order to collect a set of samples in the form of bitstrings . The bitstrings are then used to calculate the cross-entropy benchmark fidelity via a classical computer, given by

This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.

References

  1. ↑ Knapp, Alex, ed. (2018). "The 2019 30 under 30 Inventing the future from the atom up - Science". Forbes.
  2. 1 2 3 4 5 6 7 "Teenager Finds Classical Alternative to Quantum Recommendation Algorithm | Quanta Magazine". Quanta Magazine. Retrieved 2018-11-14.
  3. ↑ "Davidson Fellows 2014". www.davidsongifted.org. Retrieved 2018-11-14.
  4. ↑ Kerenidis, Iordanis; Prakash, Anupam (2016-03-29). "Quantum Recommendation Systems". arXiv: 1603.08675 [quant-ph].
  5. ↑ "Challenges in Quantum Computation | Simons Institute for the Theory of Computing". simons.berkeley.edu. 9 January 2018. Retrieved 2018-11-14.
  6. ↑ "Graduating Natural Sciences Students Make Their Mark at UT Austin" . Retrieved 2018-11-14.
  7. ↑ "A Student Took Down One of Quantum Computing's Top Applications—Now What?". Singularity Hub. 2018-08-12. Retrieved 2018-11-14.
  8. 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.
  9. ↑ "Maybe We Don't Need Quantum Computing After All - Developer.com". www.developer.com. 7 August 2018. Retrieved 2018-11-14.
  10. ↑ "Ewin Tang". Forbes. Retrieved 2018-11-14.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.