Related Research Articles
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.
Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing-computable. Super-Turing computing, introduced in the early 1990's by Hava Siegelmann, refers to such neurological inspired, biological and physical realizable computing; It became the mathematical foundations of Lifelong Machine Learning. Hypercomputation, introduced as a field of science in the late 1990s, is said to be based on the Super Turing but it also includes constructs which are philosophical. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that can correctly evaluate every statement in Peano arithmetic.
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
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.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
Quantum programming is the process of assembling sequences of instructions, called quantum circuits, that are capable of running on a quantum computer. Quantum programming languages help express quantum algorithms using high-level constructs. The field is deeply rooted in the open-source philosophy and as a result most of the quantum software discussed in this article is freely available as open-source software.
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.
Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massachusetts Institute of Technology.
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 computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.
In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of previous tests can influence the tests performed next.
John Harrison Watrous is a professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, a member of the Institute for Quantum Computing, an affiliate member of the Perimeter Institute for Theoretical Physics and a Fellow of the Canadian Institute for Advanced Research. He was a faculty member in the Department of Computer Science at the University of Calgary from 2002 to 2006 where he held a Canada Research Chair in quantum computing.
Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).
Cristopher David Moore, known as Cris Moore, is an American computer scientist, mathematician, and physicist. He is resident faculty at the Santa Fe Institute, and was formerly a full professor at the University of New Mexico.
Andrew MacGregor Childs is an American computer scientist and physicist known for his work on quantum computing. He is currently a Professor in the Department of Computer Science and Institute for Advanced Computer Studies at the University of Maryland. He also co-directs the Joint Center for Quantum Information and Computer Science, a partnership between the University of Maryland and the National Institute of Standards and Technology.
Barbara M. Terhal is a theoretical physicist working in quantum information and quantum computing. She is a researcher at the Forschungszentrum Jülich, a professor in the EEMCS Department at TU Delft, as well as the Research Lead for the Terhal Group at QUTech. Her research concerns many areas in quantum information theory, including entanglement detection, quantum error correction, fault-tolerant quantum computing and quantum memories.
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.
Aram Wettroth Harrow is a professor of physics in the Massachusetts Institute of Technology's Center for Theoretical Physics.
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).
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
- ↑ Richard Cleve at the IQC directory.
- ↑ Richard Cleve at the University of Waterloo website.
- ↑ Richard Cleve at the Mathematics Genealogy Project.
- 1 2 3 2008 CAP/CRM Prize in Theoretical and Mathematical Physics
- ↑ Barenco, Adriano; Charles H. Bennett; Richard Cleve; David P. DiVincenzo; Norman Margolus; Peter Shor; Tycho Sleator; John A. Smolin; Harald Weinfurter (1995-11-01). "Elementary gates for quantum computation". Physical Review A. 52 (5): 3457–3467. arXiv: quant-ph/9503016 . Bibcode:1995PhRvA..52.3457B. doi:10.1103/PhysRevA.52.3457. PMID 9912645 . Retrieved 2009-08-18.
- ↑ Childs, Andrew M.; Richard Cleve; Enrico Deotto; Edward Farhi; Sam Gutmann; Daniel A. Spielman (2003). "Exponential algorithmic speedup by a quantum walk". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. San Diego, CA, USA: ACM. pp. 59–68. arXiv: quant-ph/0209131 . doi:10.1145/780542.780552. ISBN 1-58113-674-9 . Retrieved 2009-08-18.
- ↑ Beals, Robert; Harry Buhrman; Richard Cleve; Michele Mosca; Ronald de Wolf (2001). "Quantum lower bounds by polynomials". J. ACM. 48 (4): 778–797. arXiv: quant-ph/9802049 . doi:10.1145/502090.502097 . Retrieved 2009-08-18.
- ↑ Buhrman, Harry; Richard Cleve; Avi Wigderson (1998). "Quantum vs. classical communication and computation". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 63–68. arXiv: quant-ph/9802040 . doi:10.1145/276698.276713. ISBN 0-89791-962-9 . Retrieved 2009-08-18.
- ↑ List of editors of Quantum Information & Computation
| International | |
|---|---|
| Academics | |
   | This article about a Canadian scientist is a stub. You can help Wikipedia by expanding it. |