“Gil Kalai”的意思、由来-开放百科全书

Gil Kalai received his Ph.D. from Hebrew University in 1983, under the supervision of Micha Perles,^[1] and joined the Hebrew University faculty in 1985 after a postdoctoral fellowship at the Massachusetts Institute of Technology.^[2] 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.^[3] 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] In 2018 he was a plenary speaker with talk Noise Stability, Noise Sensitivity and the Quantum Computer Puzzle at the International Congress of Mathematicians in Rio de Janeiro.

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.

See also

References

1. ^{{MathGenealogy|name=Gil Kalai|id=62336}}.
2. ^Profile at the Technical University of Eindhoven as an instructor of a minicourse on polyhedral combinatorics.
3. ^¹Profile at Yale CS department.
4. ^{{citation|first=Gil|last=Kalai|contribution=A subexponential randomized simplex algorithm|title=Proc. 24th ACM Symp. Theory of Computing (STOC 1992)|year=1992|pages=475–482}}.
5. ^{{citation|doi=10.1090/S0002-9939-96-03732-X|first1=Ehud|last1=Friedgut|first2=Gil|last2=Kalai|title=Every monotone graph property has a sharp threshold|journal=Proceedings of the American Mathematical Society|volume=124|year=1996|pages=2993–3002|url=http://www.ams.org/proc/1996-124-10/S0002-9939-96-03732-X/}}.
6. ^{{citation|doi=10.1090/S0273-0979-1993-00398-7|first1=Jeff|last1=Kahn|first2=Gil|last2=Kalai|arxiv=math.MG/9307229 |title=A counterexample to Borsuk's conjecture|journal=Bulletin of the American Mathematical Society|volume=29|year=1993|pages=60–62}}.
7. ^{{citation|doi=10.1090/S0273-0979-1992-00285-9|first1=Gil|last1=Kalai|first2=Daniel J.|last2=Kleitman|authorlink2=Daniel Kleitman|title=A quasi-polynomial bound for the diameter of graphs of polyhedra|journal=Bulletin of the American Mathematical Society|volume=26|year=1992|pages=315–316|url=http://www.ams.org/bull/1992-26-02/S0273-0979-1992-00285-9/|arxiv=math/9204233}}.
8. ^Yad Hanadiv, Rothschild Prize.
9. ^{{cite web|title=A Magyar Tudományos Akadémia újonnan megválasztott tagjai (The newly elected members of the Hungarian Academy of Sciences)|website=Magyar Tudományos Akadémia (mta.hu)|date=2 May 2016|url=http://mta.hu/kozgyules2016/a-magyar-tudomanyos-akademia-ujonnan-megvalasztott-tagjai-106411}}
10. ^How Quantum Computers Fail by Gil Kalai (2011)

Biography

Kalai's conjectures on quantum computing

See also

References

External links