Microsoft Q# Coding Contest - Winter 2019

13 problems from Microsoft Q# Coding Contest - Winter 2019 (contest 1116), difficulty -. 12/13 solutions verified against sample I/O.

13 items

Microsoft Q# Coding Contest - Winter 2019

Special | 13 problems | 12/13 verified | Difficulty - | 11m 14s

#	Problem	Rating	Tags	Accepted	Time	✓
A1	[Generate state	00\u27e9 +	01\u27e9 +	10\u27e9](https://codeforces.com/problemset/problem/1116/A1)
A2	Generate equal superposition of four basis states		*special	184	2m 38s	✓
B1	Distinguish three-qubit states		*special	136	48s	✓
B2	Not A, not B or not C?		*special	62	58s	✓
C1	Alternating bits oracle		*special	267	40s	✓
C2	``Is the bit string periodic?'' oracle		*special	189	41s	✓
C3	``Is the number of ones divisible by 3?'' oracle		*special	187	48s	✓
D1	Block diagonal matrix		*special	278	43s	✓
D2	Pattern of increasing blocks		*special	236	47s	✓
D3	X-wing fighter		*special	207	56s	✓
D4	TIE fighter		*special	171	41s	✓
D5	Creeper		*special	152	51s	✓
D6	Hessenberg matrix		*special	81	43s	✓

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116A2 - Generate equal superposition of four basis states

We start with a register of qubits initialized in the all-zero computational basis state. Alongside this, we are given four classical bitstrings of length $N$, each describing one computational basis state on these qubits.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116D6 - Hessenberg matrix

We are asked to implement a quantum operation on a small number of qubits (2 to 4) such that the unitary matrix representing it has an upper Hessenberg form.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116D5 - Creeper

We are given a very specific 8×8 pattern describing where a 3-qubit unitary matrix has non-negligible entries. The matrix is not arbitrary, it is extremely sparse and structured, and the task is to implement any quantum circuit on 3 qubits whose unitary matches this sparsity…

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116D4 - TIE fighter

We are asked to implement a quantum operation on an array of $N$ qubits, where $N$ ranges from 2 to 5. The core requirement is that the operation's unitary matrix has a very particular pattern: a central 2x2 submatrix filled with non-zero values, anti-diagonals in the top-left…

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116D3 - X-wing fighter

We are asked to implement a unitary operation on a quantum register consisting of $N$ qubits, where $2 le N le 5$. The unitary is represented as a $2^N times 2^N$ matrix, and it must have non-zero entries only on the main diagonal and the anti-diagonal.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116D2 - Pattern of increasing blocks

We are asked to construct a quantum operation on $N$ qubits whose matrix, in the computational basis, has a very rigid block structure. The full unitary is a $2^N times 2^N$ matrix, and we are not required to compute or print it explicitly.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116D1 - Block diagonal matrix

We are asked to implement a unitary operation on an array of $N$ qubits, where $2 le N le 5$, such that the matrix representing the operation has a very specific block-diagonal structure.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116C3 - ``Is the number of ones divisible by 3?'' oracle

We are given a small register of qubits that encode a bitstring and an additional single qubit that acts as an output accumulator.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116C2 - ``Is the bit string periodic?'' oracle

We are asked to implement a quantum oracle that checks whether a given bit string is periodic. In practical terms, imagine we have an array of $N$ qubits, each representing a bit, and a separate output qubit.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116B2 - Not A, not B or not C?

We are asked to work with a single qubit that is guaranteed to be in one of three specific quantum states: $ Our goal is not to identify which state the qubit is in, but to return a number corresponding to a state we are sure the qubit is not in.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116C1 - Alternating bits oracle

We are asked to implement a "quantum oracle" that checks whether a binary vector alternates. That means for an input array of bits x[0..N-1], we need to determine if no two consecutive bits are the same.

Practice › Codeforces Solutions › Microsoft Q# Coding Contest - Winter 2019 ›

CF 1116B1 - Distinguish three-qubit states

We are given three qubits in one of two specific entangled states, each a superposition of three computational basis states with complex coefficients derived from the cube roots of unity. The two states differ only in the phase factors applied to the second and third qubits.