## No. 1 in C-not major

## Program a quantum computer, win a trip to Sochi

**Deadline:** 15th of January 2019, AoE. **Notification:** 30th January 2019.

**Open to:** ETH Zurich students (bachelors, masters, PhD), in teams of 1-3.

In collaboration with ETH Zurich and the Russian Quantum Center, Squids brings you the first edition of **Quantum Symphony**, a competition on quantum programming. This pilot edition is open to students of ETH Zurich, in teams of 1-3 students.

**The award** for the best team is a **trip to Sochi, Russia**, for a quantum computing winter school and hackathon organised by the Russian Quantum Center, to take place **18-24 February 2019**. Flights and accommodation of the winning team members, as well as registration, will be covered by the Russian Quantum Center.

### How to participate

Fill out the form at the bottom of this page, telling us your NETHZ usernames. We will add you to a subgroup of gitlab for your team, where you can share or create your entry’s project. This will not be visible to other participants. We will judge the version of the projects available by the deadline. There are two tasks: create one project per task.

All** rights to work** developed by participants stay with the authors. If you choose to make your solution public and it meets Squid’s quality standards, we may link to it from Squid’s website and advertise it as a good example. We will always ask authors before doing this.

### Rules

You can submit your work in any **programming language** (e.g. Python, C++, Mathematica) or combination thereof, and any libraries that are publicly available. We trust you to be reasonable – if it’s something like assembly, or fortran we are unlikely to review it. If the final program can be run in a quantum computer like IBM’s, this is extra nice, so tools like ProjectQ, Q# or Qiskit may be useful.

For each task you should create one “project” in gitlab, which should include the **programs and documentation** explaining your solution, how it works, how to run it, and tools used.

The two tasks are exploratory in nature: there are some basic steps that can be done, and suggestions for generalisations. You can also find other ways to generalise the solution: we value creativity.

### Evaluation criteria

The submissions will be judged by a panel of researchers in quantum computing. If something is not clear or doesn’t compile, we may write to the authors for clarifications.

The criteria are quality of execution, whether the programs actually address the problems solved, quality of documentation, efficiency, generality and elegance of the solution.

## The tasks

### 1. Quantum pigeon hole simulation

The pigeonhole principle is naturally intuitive in the classical world: if you put three pigeons in two pigeonholes at least two of the pigeons end up in the same hole. However, it turns out that this is not necessarily true in the quantum world! [1]

In this task, you will have to model the *quantum pigeonhole principle*, an example of so-called *pre- and post-selection logical paradoxe*s which occur in quantum mechanics [2].

#### Resources

[1] Y. Aharonov, F. Colombo, S. Popescu, I. Sabadini, D. C. Struppa: “The quantum pigeonhole principle and the nature of quantum correlations”, 2014; arXiv:1407.3194.

[2] Matthew F. Pusey, Matthew S. Leifer: “Logical pre- and post-selection paradoxes are proofs of contextuality”, 2015, EPTCS 195, 2015, pp. 295-306; arXiv:1506.07850. DOI: 10.4204/EPTCS.195.22.

#### Subtasks

Your program should simulate the experiment, which in principle can be done at different levels of abstraction.

*Mandatory*

- Simulate the counterfactual paradox in [1].
- Compute the weak values for the paradox.
- Allow for different pre- and post-selections.

*Extra*

- Model the pointer as a quantum system undergoing a joint evolution with the system measured.
- For a given arbitrary setting, try to find whether there are pre- and post-selections that lead to a pre- and post-selection.

### 2. Quantum transversals

We start with the set \(G\) of all \(N\)-bit strings, for example for \(N=3\), $$G=\{000, 001, 010, 100, 011, 101, 110, 111\}.$$

Now we consider a symmetry group acting on \(N\) elements; for example the fully symmetric group $$S_3=\{123, 132, 213, 231, 312, 321\},$$ which represents all permutations of the three elements. There could be other groups, like \(S_2 \times S_1 = \{123, 213\}\), which only allow for permutations of the two first elements.

Our original set \(G\) can be partitioned into a maximal collection of subsets, each one invariant under the action of the permutation group. In the case of \(S_3\) we have $$G_0= \{000\}, \quad G_1=\{001, 010, 100\},\quad G_2=\{011, 101, 110\}, \quad G_3=\{111\}.$$

A **transversal** is then a set containing exactly one element from each member of the collection, for example $$T= \{000, 010, 110, 111\}.$$

Another possible transversal could be for example \(T’=\{000, 100, 110, 111\} = (213) \ T\), which is the result of acting with the permutation \((213)\) from the symmetry group on the elements of \(T\).

A uniform quantum superposition of the elements of the transversal \(T\) (“*quantum transversal”* for short) would be the 3-qubit state $$ \frac12 \big( \left|000\right> + \left| 010\right> + \left|110\right> + \left|111\right>\big). $$

In this task, you should write a program that receives as input the number of qubits \(N\) and a symmetry group acting on \(N\) elements, and outputs a quantum circuit that generates a quantum transversal. You are free to choose the format of the input. See [1] for a classical algorithm to find a transversal, which can be used as a preparatory step.

#### Resources

[1] Nicolas Borie: “Generating tuples of integers modulo the action of a permutation group and applications”, 2012; arXiv:1211.6261.

#### Subtasks

*Mandatory*

- Output the final state (a uniform superposition of a transversal) for the fully symmetric group \(S_N\).
- The program should also output the circuit that generates the quantum transversal.
- Allow for an extra input \(\pi \in S\), which is a permutation in the symmetry group, and output the effect of this permutation on the transversal.

*Extra*

- Allow for any symmetric group on \(N\) elements.
- Find a way to order the transversal, and let the user also input their preferred transversal (e.g. whether they want a superposition of the elements of \(T\) or \(T’\) in the example above).

## Registration

Please register before the 13th of January so we can create the subgroup in time for you to troubleshoot the submission. Submission deadline for all the projects to be in the gitlab subgroup is the 15th of January 2019, AoE.

## Questions and other queries

For most questions which may be of interest to other participants, use the forum below. For confidential queries only, email Lídia and Nuriya at info [at] squids.ch .

Ask a question directly below.