Program: Institute for Theoretical Computer Science and Communications (ITCSC) Summer Research Program, The Chinese University of Hong Kong

Supervisor: Prof. Andrej Bogdanov, Department of Computer Science and Engineering, The Chinese University of Hong Kong

Co-author: Xin Lyu, Yao Class, Tsinghua University

Introduction

Suppose we have two probability distributions p and q, both defined on fixed-length bit strings (say length-3), and with disjoint supports. Here is an example, where the probability mass is denoted below a string:

You can check that p and q have disjoint supports.

The preliminary question is: given a random sample from either p or q (with probability 1/2 each), how good could an algorithm be at guessing which distribution it is from? Of course, the problem would be trivial if the sample is fully known. What if the algorithm is allowed to query only two bits of the sample in any order?

Before we dive into the problem, let's cover some backgrounds first. The algorithm is called a distinguisher, and there are different types of distinguishers:

• Non-adaptive distinguishers. These always look at fixed bit positions of the sample, say the first and the second bits.
• Adaptive distinguishers. These could have some strategies of determining which bit positions to look at. An example is below.
• Quantum distinguishers. These are quantum circuits behind the scene, and the querying process is implemented with quantum oracles.

In order to evaluate the performance of a distinguisher, let's define a distinguishing advantage for it:

Some simple calculations yield the advantage of this distinguisher, which is one third:

It is obvious to see that there are three different non-adaptive distinguishers, and they all perform worse than the adaptive one:

Research Question

Please refer to the slides below.

In this project, we have constructed several examples with various gaps and ratios of the advantages. In the last example, we came up with a construction inspired by the Deutsch-Jozsa algorithm, and proved that a quantum distinguisher could perfectly distinguish between the two distributions after querying half of the bits, while classical distinguishers all fail to achieve non-zero advantage without revealing all the bits.

Please refer to the slides for more information.

Materials

Slides

Situated on the hilltops of Ma Liu Shui, The Chinese University of Hong Kong (CUHK) features a complicated shuttle bus system to help its students and employees commute in the vast campus.

Although the university provides maps with abstract layouts for the shuttle bus system, newcomers usually find it difficult to identify the physical locations of the bus stops. In fact, two seemingly adjacent stops could be a mile apart, with tens of meters of difference in elevation.

To assist freshman and visitors with moving around, I drew a map of the shuttle bus system with a physical layout. A PDF version is available here.

In January 2019, HSFZ (华师附中, the Affiliated High School of South China Normal University) alumni in Hong Kong organized a joint information session on admissions for current HSFZ students. Acting as the design lead of the team, I was responsible for the visual identity of the campaign. I also delivered information on CUHK admission at the session.

The color palette, consisting of orange, purple, and blue, was sampled from the emblems of the three universities.

The logo was made up of three overlapping circles, ordered by the ages of the corresponding universities.

The name 乾貨舖 stemmed from the word 乾貨 (lit. dried/preserved food), which is a common metaphor for informative content in Chinese.

The poster for the event was drawn with isometric voxels in Sketch, where connected H's in the abbreviations of the universities formed a ladder, signifying higher education.

The mosaic patterns in our header images resembled the interior of MTR stations. They were generated with the following Mathematica code:

Program: Undergraduate Summer Research Internship Program, Faculty of Engineering, The Chinese University of Hong Kong

Supervisor: Prof. Chen Lian-Kuan, Department of Information Engineering, The Chinese University of Hong Kong

Prometheus is an open-source implementation of a screen-to-camera communication system on iOS. It transfers a file by displaying a sequence of QR codes, each carrying a file segment. The receiver then decodes the QR codes and reconstructs the file from the received segments.

Moreover, Prometheus features a few innovative techniques for improving its throughput and robustness. For details, please refer to the report and the slides.

Screenshots

Demo Video

Materials

Report

Presentation Slides

GitHub repo