codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1002E1.md (1669B)


      1 Source: https://codeforces.com/problemset/problem/1002/E1
      2 
      3 E1. Bernstein-Vazirani algorithm
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a quantum oracle - an operation on *N* + 1 qubits which implements a function ![](https://espresso.codeforces.com/ca923da5e61e139eb5596a3b9e34cc7ef42d1433.png). You are guaranteed that the function *f* implemented by the oracle is scalar product function (oracle from problem D1):
     22 
     23 ![](https://espresso.codeforces.com/2b31a0d1ff4af2d7c1af23391f540a01218c8fa7.png)
     24 
     25 Here ![](https://espresso.codeforces.com/b27ec8b8056386de828da0df174348afa7d29512.png) (an array of *N* integers, each of which can be 0 or 1).
     26 
     27 Your task is to reconstruct the array ![](https://espresso.codeforces.com/71fa108edb785ca9f729fa3cd5ad18556dd682e4.png). Your code is allowed to call the given oracle only once.
     28 
     29 You have to implement an operation which takes the following inputs:
     30 
     31 * an integer *N* - the number of qubits in the oracle input (1 ≤ *N* ≤ 8),
     32 * an oracle *Uf*, implemented as an operation with signature ((Qubit[], Qubit) => ()), i.e., an operation which takes as input an array of qubits and an output qubit and has no output.
     33 
     34 The return of your operation is an array of integers of length *N*, each of them 0 or 1.
     35 
     36 Your code should have the following signature:
     37 
     38 ```
     39 namespace Solution {  
     40     open Microsoft.Quantum.Primitive;  
     41     open Microsoft.Quantum.Canon;  
     42   
     43     operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Int[]  
     44     {  
     45         body  
     46         {  
     47             // your code here  
     48         }  
     49     }  
     50 }
     51 ```