quantum-computer

You are currently browsing articles tagged quantum-computer.

Theory News 01/2018

  1. Tháng 1 vừa qua có rất nhiều bàn luận xung quanh việc có nên áp dụng blind reviews (double or single) cho các hội nghị lý thuyết (FOCS/STOC/SODA) hay không. Các tranh luận này có lên hệ tới thí nghiệm gần đây của Tomkins, Zhang và Heavlin (https://arxiv.org/pdf/1702.00502.pdf) giữa single blind reviews và double blind reviews áp dụng cho hội nghị WSDM 2017.
    • Người ủng hộ bao gồm Suresh và Rasmus. Hai người tiến hành thí nghiệm double blind reviews với ALENEX. Link: http://blog.geomblog.org/2018/01/report-on-double-blind-reviewing-in.html. Mục tiêu của blind reviews nói chung là giảm bias trong quá trình bình duyệt các papers. Có nhiều nguyên nhân, nhưng nổi bật nhất là bias gây ra tên tuổi của (các) tác giả của các paper. Kể cả người bình duyệt không muốn bias nhưng nếu họ review các paper của các tác giả nổi tiếng thì khả năng cao họ vẫn bias (mà họ không biết). Đọc thêm một số luận điểm của Suresh tại đây (http://blog.geomblog.org/2018/01/double-blind-review-continuing.html)
    • Người phản đối gồm: James Lee, Boaz Barak, Oded Goldreich và một số khác. Các tranh luận của nhóm này xét tới các yếu tố rất đặc thù của ngành lý thuyết. Một số luận điểm của Oded (http://www.wisdom.weizmann.ac.il/~oded/on-anony.html): (i) Bias trong submissions nhiều khi không phải là do ai là tác giả mà là do cách format hoặc cách trình bày kết quả. Các hội nghị lý thuyết đặc biệt bias các công trình có tính kĩ thuật và độ phức tạp cao hơn các công trình khác. Do đó, cho dù có sử dụng double blind reviews thì bias thực sự vẫn không được giải quyết, (ii) Nhiều khi không khó để có thể suy ra tên tác giả. Hiện nay các nghiên cứu có xu hướng được upload lên arxiv (hay trang cá nhân) trước khi submit. Đương nhiên là không thể (và không nên) cấm các nhà nghiên cứu upload các nghiên cứu của họ lên (mục đích nói chung của conference cuối cùng cũng là quản bá các ý tưởng). (iii) Giả sử một reviewer đã được nghe về công trình nghiên cứu trước khi nhận được review request từ conference. Làm sao reviewer đó biết được tác giả của công trình trình được submit và công trình mà anh/chị ta nghe được trước đó đều là 1, vì trong trường hợp 2 nhóm tác giả khác nhau đề xuất cùng một công trình thì cần phải có cơ chế giải quyết xung đột và (iv) các reviewers có thể không trung thực. Ví dụ reviewer quen biết tác giả nhưng giả vờ không biết để nói tốt hơn mức thực sự của bài báo. Đọc thêm một số bình luận khác: Boaz Barak (https://windowsontheory.org/2018/01/11/on-double-blind-reviews-in-theory-conferences/), Omer Reingold (https://theorydish.blog/2018/01/25/just-defined-bias-not-sure/).
    • Một số khác ủng hộ double blind reviews nhưng cho rằng không thể thực hiện được đối với các hội nghị lý thuyết, ví dụ Michael Mitzenmacher(http://mybiasedcoin.blogspot.com/2018/01/double-blind-alenex.html).
  2. Tháng này mình học được bài toán Ballot của Bertrand. Bài toán như sau: giả sử trong một cuộc bầu cử, $A$ nhận được $p$ phiếu và $B$ nhận được $q$ phiếu, trong đó $p$ > $q$. Tìm xác suất trong quá trình kiểm phiếu, A luôn có số phiếu nhiều hơn B. Kết quả là một con số rất đẹp:

    $\frac{p-q}{p+q}$

    Xem tại: https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem.

  3. Timeline của Computer Science, by Scott Aaronson. Link : https://www.scottaaronson.com/blog/?p=524. Post này đã cũ nhưng khá thú vị, đặc biệt bạn nào muốn tìm hiểu lịch sử khoa học máy tính thì không thể bỏ qua post này.
  4. Giả sử bạn muốn sinh một số nguyên ngẫu nhiên từ 1 tới $N$ , với phân phối (gần) đều. Nếu bạn có một hàm trả lại số nguyên ngẫu nhiên $x$ có 32 bít ($N$ cũng 32 bít) thì bạn có thể sử dụng hàm $x \% N$ để sinh ra số từ 1 đến $N$. Hàm này gọi là một fair map. Tuy nhiên, hàm modulo thực hiện rất chậm trên máy tính. Daniel Lemire đề xuất một fair map khác nhanh hơn, đó là:

    $(N*x)/2^{32}$

    Tính hàm này chỉ cần một phép nhân và một vài phép dịch bít. Mình thấy đây là một hàm khá thú vị! Xem post tại đây: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/.

  5. Tweet của Moritz Hardt dành cho các bạn đang apply vào grad school "It's that time of the year to keep in mind that the typical start of a successful academic career is getting rejected from a bunch of good grad schools." Tweet liên quan của Ryan Williams: " I was rejected from EVERY grad school I applied to. (I applied to almost all of the usual places.) Funnily, I was awarded an NSF fellowship. I HAD AN NSF FELLOWSHIP, BUT NO PHD PROGRAM TO GO TO. Luckily, Cornell let me use it for an MEng, and I used that to write up a SODA paper. " Còn một số chia sẽ thú vị nữa của một vài theorist nổi tiếng. Link: https://twitter.com/mrtz/status/950493433822560257.
  6. Có thể bạn đã nghe rất nhiều về các phát kiến nhảy vọt trong Quantum Computer gần đây. Ví dụ D-Wave 2000Q có 2000 qbits. Thực tế, chỉ cần xây dựng được máy tính có 50-100 qbits thôi đã là một bước đại nhảy vọt rồi. Tại sao D-Wave 2000Q lại không phải là một đại nhảy vọt (mà dù đó cũng là một bước tiến lớn)? Vấn đề nằm ở chất lượng q-bits. Thực tế, cho đến giờ người ta vẫn cho rằng cần rất nhiều năm nữa mới có thể xây dựng được một máy tính lượng tử trong thực tế với các q-bits chất lượng cao. Vậy các loại máy tính lượng tử gần đây với hàng trăm q-bits là cái gì. Câu trả lời có trong survey của John Preskill: https://arxiv.org/pdf/1801.00862.pdf. Survey này Preskill viết cho những ngườ không có nhiều background về mặt kĩ thuật, để có thể hiểu về hiện trạng của Quantum Computer.
    • Một số nhà nghiên cứu lý thuyết còn cho không thể xây dựng được các máy tính lượng tử có q-bit chất lượng cao. Ví dụ Gil Kalai cho rằng không thể (xem tại http://www.ma.huji.ac.il/~kalai/Qitamar.pdf).
  7. Liệu chúng ta có phải luôn cần làm experiments để validate các công trình nghiên cứu khoa học. Not always! Đọc essay của Ullman tại: https://cacm.acm.org/magazines/2015/9/191183-experiments-as-research-validation/fulltext.

Tags: , , , ,