Gil Kalai

Gil Kalai, 1986
Gil Kalai, 2007

Gil Kalai (born 1955) is the Henry and Manya Noskwith Professor of Mathematics at the Hebrew University of Jerusalem, and adjunct professor of mathematics and of computer science at Yale University.[1]

Biography

Gil Kalai received his Ph.D. from Hebrew University in 1983, under the supervision of Micha Perles,[2] and joined the Hebrew University faculty in 1985 after a postdoctoral fellowship at the Massachusetts Institute of Technology.[3] He was the recipient of the Pólya Prize in 1992, the Erdős Prize of the Israel Mathematical Society in 1993, and the Fulkerson Prize in 1994.[1] He is known for finding variants of the simplex algorithm in linear programming that can be proven to run in subexponential time,[4] for showing that every monotone property of graphs has a sharp phase transition,[5] for solving Borsuk's problem (known as Borsuk's conjecture) on the number of pieces needed to partition convex sets into subsets of smaller diameter,[6] and for his work on the Hirsch conjecture on the diameter of convex polytopes and in polyhedral combinatorics more generally.[7]

He was the winner of the 2012 Rothschild Prize in mathematics.[8] From 1995 to 2001, he was the Editor-in-Chief of the Israel Journal of Mathematics. In 2016, he was elected honorary member of the Hungarian Academy of Sciences[9]

Kalai's conjectures on quantum computing

Conjecture 1 (No quantum error correction). The process for creating a quantum error correcting code will necessarily lead to a mixture of the desired codewords with undesired codewords. The probability of the undesired codewords is uniformly bounded away from zero. (In every implementation of quantum error-correcting codes with one encoded qubit, the probability of not getting the intended qubit is at least some δ > 0, independently of the number of qubits used for encoding.)

Conjecture 2. A noisy quantum computer is subject to noise in which information leaks for two substantially entangled qubits have a substantial positive correlation.

Conjecture 3. In any quantum computer at a highly entangled state there will be a strong effect of error-synchronization.

Conjecture 4. Noisy quantum processes are subject to detrimental noise.[10]

See also

References

  1. 1 2 Profile at Yale CS department.
  2. ↑ Gil Kalai at the Mathematics Genealogy Project.
  3. ↑ Profile at the Technical University of Eindhoven as an instructor of a minicourse on polyhedral combinatorics.
  4. ↑ Kalai, Gil (1992), "A subexponential randomized simplex algorithm", Proc. 24th ACM Symp. Theory of Computing (STOC 1992), pp. 475–482.
  5. ↑ Friedgut, Ehud; Kalai, Gil (1996), "Every monotone graph property has a sharp threshold", Proceedings of the American Mathematical Society 124: 2993–3002, doi:10.1090/S0002-9939-96-03732-X.
  6. ↑ Kahn, Jeff; Kalai, Gil (1993), "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society 29: 60–62, arXiv:math.MG/9307229, doi:10.1090/S0273-0979-1993-00398-7.
  7. ↑ Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society 26: 315–316, doi:10.1090/S0273-0979-1992-00285-9.
  8. ↑ Yad Hanadiv, Rothschild Prize.
  9. ↑
  10. ↑ How Quantum Computers Fail by Gil Kalai

External links

This article is issued from Wikipedia - version of the Monday, May 02, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.