{"problem":{"name":"B2. Distinguish GHZ state and W state","description":{"content":"You are given _N_ qubits (2 ≤ _N_ ≤ 8) which are guaranteed to be in one of the two states: *   state, or *   state.Your task is to perform necessary operations and measurements to figure out which s","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1002B2"},"statements":[{"statement_type":"Markdown","content":"You are given _N_ qubits (2 ≤ _N_ ≤ 8) which are guaranteed to be in one of the two states:\n\n*   state, or\n*   state.Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was GHZ state or 1 if it was W state. The state of the qubits after the operations does not matter.\n    \n    You have to implement an operation which takes an array of _N_ qubits as an input and returns an integer.\n    \n    Your code should have the following signature:\n    \n    namespace Solution {\n        open Microsoft.Quantum.Primitive;\n        open Microsoft.Quantum.Canon;\n    \n        operation Solve (qs : Qubit\\[\\]) : Int\n        {\n            body\n            {\n                // your code here\n            }\n        }\n    }\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定 #cf_span[N] 个量子比特（#cf_span[2 ≤ N ≤ 8]），它们保证处于以下两种状态之一：\n\n你的任务是执行必要的操作和测量，以确定它处于哪种状态，并在是 GHZ 态时返回 0，在是 W 态时返回 1。操作后量子比特的状态无关紧要。\n\n你需要实现一个操作，该操作以一个包含 #cf_span[N] 个量子比特的数组作为输入，并返回一个整数。\n\n你的代码应具有以下签名：\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 2 \\leq N \\leq 8 $.  \nLet $ \\mathcal{H} = (\\mathbb{C}^2)^{\\otimes N} $ be the Hilbert space of $ N $ qubits.  \nLet $ |\\text{GHZ}\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle^{\\otimes N} + |1\\rangle^{\\otimes N}) $ and $ |\\text{W}\\rangle = \\frac{1}{\\sqrt{N}} \\sum_{i=1}^N |0\\rangle^{\\otimes (i-1)} |1\\rangle |0\\rangle^{\\otimes (N-i)} $ be the two possible quantum states.\n\nLet $ \\psi \\in \\{ |\\text{GHZ}\\rangle, |\\text{W}\\rangle \\} $ be the unknown initial state of the $ N $-qubit system.\n\n**Constraints**  \n1. The system is initialized in either $ |\\text{GHZ}\\rangle $ or $ |\\text{W}\\rangle $.  \n2. Only quantum operations (unitaries, measurements) on the $ N $ qubits are permitted.  \n3. The goal is to distinguish between the two states with certainty.  \n4. The final state of the qubits after measurement is irrelevant.  \n\n**Objective**  \nDesign a quantum algorithm (measurement strategy) that, given access to a single copy of $ \\psi $, outputs:  \n$$\n\\begin{cases}\n0 & \\text{if } \\psi = |\\text{GHZ}\\rangle \\\\\n1 & \\text{if } \\psi = |\\text{W}\\rangle\n\\end{cases}\n$$  \nwith probability 1.  \n\nImplement an operation $ \\mathcal{A} : \\mathcal{H} \\to \\{0,1\\} $ that performs the required measurement and returns the correct label.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1002B2","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}