{"id":91835,"date":"2026-08-08T14:16:56","date_gmt":"2026-08-08T06:16:56","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/91835.html"},"modified":"2026-08-08T14:16:56","modified_gmt":"2026-08-08T06:16:56","slug":"deutsch-jozsa-%e7%ae%97%e6%b3%95%e7%9a%84-c-%e8%af%ad%e8%a8%80%e6%95%b0%e5%80%bc%e9%aa%8c%e8%af%81%e6%8a%a5%e5%91%8a","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/91835.html","title":{"rendered":"Deutsch-Jozsa \u7b97\u6cd5\u7684 C \u8bed\u8a00\u6570\u503c\u9a8c\u8bc1\u62a5\u544a"},"content":{"rendered":"

\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

\u9a8c\u8bc1\u5bf9\u8c61：\u539f\u6587\u300aDeutsch-Jozsa\u7b97\u6cd5\u7684\u6570\u5b66\u57fa\u7840\u3001\u7b97\u6cd5\u63a8\u5bfc\u4e0e\u91cf\u5b50\u5b9e\u73b0\u300b\u7b2c\u4e09\u3001\u56db\u8282\u7684\u6838\u5fc3\u6570\u5b66\u7ed3\u8bba
\n\u9a8c\u8bc1\u65b9\u6cd5：\u7528\u7eaf C（C11，\u4ec5\u4f9d\u8d56 complex.h \/ math.h，\u65e0\u7b2c\u4e09\u65b9\u91cf\u5b50\u8ba1\u7b97\u5e93）\u5b9e\u73b0\u4e00\u4e2a\u5b8c\u6574\u7684\u6001\u77e2\u91cf（state-vector）\u6a21\u62df\u5668，\u4ece\u96f6\u6784\u9020 2n+12^{n+1}<\/span><\/span>2<\/span><\/span>n<\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7ef4\u5e0c\u5c14\u4f2f\u7279\u7a7a\u95f4，\u663e\u5f0f\u6267\u884c Hadamard \u53d8\u6362\u3001Oracle \u76f8\u4f4d\u56dekickback\u4e0e\u6d4b\u91cf，\u9010\u6bd4\u7279\u6253\u5370\u4e2d\u95f4\u6001\u5e76\u4e0e\u8bba\u6587\u516c\u5f0f\u9010\u9879\u6bd4\u5bf9
\n\u7ed3\u8bba：\u5168\u90e8 72 \u7ec4\u529f\u80fd\u6027\u6d4b\u8bd5（n=1n=1<\/span><\/span>n<\/span><\/span>=<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u5230 1818<\/span><\/span>18<\/span><\/span><\/span><\/span><\/span>，\u542b\u5e38\u6570\/\u5e73\u8861\/\u968f\u673a\u4eff\u5c04\/\u5bf9\u6297\u6784\u9020\u56db\u7c7b Oracle）\u4e0e Theorem 3.1 \u7684\u7ecf\u5178\u67e5\u8be2\u4e0b\u754c\u5728 n=1n=1<\/span><\/span>n<\/span><\/span>=<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u5230 1212<\/span><\/span>12<\/span><\/span><\/span><\/span><\/span> \u4e0a\u5168\u90e8\u7cbe\u786e\u5339\u914d（\u6570\u503c\u8bef\u5dee <10\u22129<10^{-9}<\/span><\/span><<\/span><\/span><\/span><\/span>1<\/span>0<\/span><\/span>\u2212<\/span>9<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u7ecf\u5178\u4e0b\u754c\u4e3a\u7cbe\u786e\u76f8\u7b49，\u975e\u8fd1\u4f3c）<\/p>\n

\n

\u4e00\u3001\u9a8c\u8bc1\u8bbe\u8ba1\u4e0e\u7f16\u7801\u7ea6\u5b9a<\/h3>\n

1.1 \u6001\u7a7a\u95f4\u7f16\u7801<\/h4>\n

\u6a21\u62df\u5668\u628a n+1n+1<\/span><\/span>n<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u4e2a\u91cf\u5b50\u6bd4\u7279（nn<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span> \u4f4d\u8f93\u5165\u5bc4\u5b58\u5668 xx<\/span><\/span>x<\/span><\/span><\/span><\/span><\/span> + 1 \u4f4d\u8f85\u52a9\u6bd4\u7279 yy<\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>）\u7f16\u7801\u4e3a\u4e00\u4e2a\u957f\u5ea6 2n+12^{n+1}<\/span><\/span>2<\/span><\/span>n<\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684 double complex \u6570\u7ec4 state[]，\u7d22\u5f15\u4e0e\u6bd4\u7279\u4e32\u7684\u5bf9\u5e94\u5173\u7cfb\u4e3a：<\/p>\n

index = (x << 1) | y<\/p>\n

\u5373\u6bd4\u7279 0（\u6700\u4f4e\u4f4d）\u56fa\u5b9a\u4e3a\u8f85\u52a9\u6bd4\u7279 yy<\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>，\u6bd4\u7279 1\u2026n1 \\\\ldots n<\/span><\/span>1<\/span><\/span>\u2026<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span> \u4f9d\u6b21\u5bf9\u5e94\u8f93\u5165\u5bc4\u5b58\u5668 x1\u2026xnx_1 \\\\ldots x_n<\/span><\/span>x<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2026<\/span><\/span>x<\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u8fd9\u4e0e\u8bba\u6587 4.1 \u8282\u7684\u521d\u59cb\u6001 \u2223\u03c80\u27e9=\u22230\u27e9\u2297n\u2297\u22231\u27e9|\\\\psi_0\\\\rangle = |0\\\\rangle^{\\\\otimes n} \\\\otimes |1\\\\rangle<\/span><\/span>\u2223<\/span>\u03c8<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u27e9<\/span><\/span>=<\/span><\/span><\/span><\/span>\u22230<\/span>\u27e9<\/span><\/span>\u2297<\/span>n<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2297<\/span><\/span><\/span><\/span>\u22231<\/span>\u27e9<\/span><\/span><\/span><\/span><\/span> \u4e25\u683c\u5bf9\u5e94：state[1] = 1（\u5373 x=0,y=1x=0, y=1<\/span><\/span>x<\/span><\/span>=<\/span><\/span><\/span><\/span>0<\/span>,<\/span><\/span>y<\/span><\/span>=<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>）\u3002<\/p>\n

1.2 \u901a\u7528\u5355\u6bd4\u7279\u95e8<\/h4>\n

\u6240\u6709\u5e7a\u6b63\u53d8\u6362（Hadamard\u3001XX<\/span><\/span>X<\/span><\/span><\/span><\/span><\/span>）\u90fd\u901a\u8fc7\u540c\u4e00\u4e2a\u51fd\u6570 apply_gate() \u5b9e\u73b0，\u5b83\u5bf9\u4efb\u610f\u76ee\u6807\u6bd4\u7279 target \u6210\u5bf9\u5904\u7406\u7d22\u5f15 ii<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>（\u8be5\u6bd4\u7279\u4e3a 0）\u4e0e j=i\u22952targetj = i \\\\oplus 2^{\\\\text{target}}<\/span><\/span>j<\/span><\/span>=<\/span><\/span><\/span><\/span>i<\/span><\/span>\u2295<\/span><\/span><\/span><\/span>2<\/span><\/span>target<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u8be5\u6bd4\u7279\u4e3a 1），\u5957\u7528 2\u00d722\\\\times2<\/span><\/span>2<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span> \u77e9\u9635：<\/p>\n

(state[i]state[j])\u2190(abcd)(state[i]state[j])
\n\\\\begin{pmatrix}\\\\text{state}[i]\\\\\\\\ \\\\text{state}[j]\\\\end{pmatrix}
\n\\\\leftarrow
\n\\\\begin{pmatrix}a & b\\\\\\\\ c& d\\\\end{pmatrix}
\n\\\\begin{pmatrix}\\\\text{state}[i]\\\\\\\\ \\\\text{state}[j]\\\\end{pmatrix}
\n<\/span><\/span>(<\/span><\/span><\/span>state<\/span><\/span>[<\/span>i<\/span>]<\/span><\/span><\/span><\/span>state<\/span><\/span>[<\/span>j<\/span>]<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u2190<\/span><\/span><\/span><\/span>(<\/span><\/span><\/span>a<\/span><\/span><\/span><\/span>c<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>b<\/span><\/span><\/span><\/span>d<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>(<\/span><\/span><\/span>state<\/span><\/span>[<\/span>i<\/span>]<\/span><\/span><\/span><\/span>state<\/span><\/span>[<\/span>j<\/span>]<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

\u5bf9\u5168\u90e8 2n+12^{n+1}<\/span><\/span>2<\/span><\/span>n<\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e2a\u7d22\u5f15\u904d\u5386\u4e00\u6b21，\u7b49\u4ef7\u4e8e\u628a\u8be5\u95e8\u4f5c\u7528\u5728 n+1n{+}1<\/span><\/span>n<\/span>+<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u4e2a\u6bd4\u7279\u5f20\u91cf\u79ef\u7a7a\u95f4\u4e0a\u7684\u5355\u4e00\u6bd4\u7279，\u800c\u4e0d\u6539\u53d8\u5176\u4f59\u6bd4\u7279\u2014\u2014\u8fd9\u6b63\u662f\u8bba\u6587 2.4 \u8282\u5f20\u91cf\u79ef\u7ed3\u6784\u7684\u76f4\u63a5\u7a0b\u5e8f\u5b9e\u73b0\u3002Hadamard \u95e8\u53d6 a=b=c=1\/2,\u00a0d=\u22121\/2a=b=c=1\/\\\\sqrt2,\\\\ d=-1\/\\\\sqrt2<\/span><\/span>a<\/span><\/span>=<\/span><\/span><\/span><\/span>b<\/span><\/span>=<\/span><\/span><\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>1\/<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span>\u00a0<\/span><\/span>d<\/span><\/span>=<\/span><\/span><\/span><\/span>\u2212<\/span>1\/<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u4e0e\u8bba\u6587\u5f0f H=12(111\u22121)H=\\\\frac{1}{\\\\sqrt2}\\\\begin{pmatrix}1&1\\\\\\\\1&-1\\\\end{pmatrix}<\/span><\/span>H<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5b8c\u5168\u4e00\u81f4\u3002<\/p>\n

1.3 Oracle \u7684\u7cbe\u786e\u5b9e\u73b0（\u800c\u975e\u8fd1\u4f3c）<\/h4>\n

\u8bba\u6587\u5b9a\u4e49 3.2：Uf\u2223x\u27e9\u2223y\u27e9=\u2223x\u27e9\u2223y\u2295f(x)\u27e9U_f|x\\\\rangle|y\\\\rangle = |x\\\\rangle|y\\\\oplus f(x)\\\\rangle<\/span><\/span>U<\/span><\/span>f<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223<\/span>x<\/span>\u27e9<\/span>\u2223<\/span>y<\/span>\u27e9<\/span><\/span>=<\/span><\/span><\/span><\/span>\u2223<\/span>x<\/span>\u27e9<\/span>\u2223<\/span>y<\/span><\/span>\u2295<\/span><\/span><\/span><\/span>f<\/span>(<\/span>x<\/span>)\u27e9<\/span><\/span><\/span><\/span><\/span>\u3002\u7531\u4e8e y\u2295f(x)y\\\\oplus f(x)<\/span><\/span>y<\/span><\/span>\u2295<\/span><\/span><\/span><\/span>f<\/span>(<\/span>x<\/span>)<\/span><\/span><\/span><\/span><\/span> \u53ea\u5728 f(x)=1f(x)=1<\/span><\/span>f<\/span>(<\/span>x<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u65f6\u7ffb\u8f6c yy<\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>，\u7a0b\u5e8f\u91cc\u5bf9\u6bcf\u4e2a xx<\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>，\u5f53 f(x)=1f(x)=1<\/span><\/span>f<\/span>(<\/span>x<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u65f6\u76f4\u63a5\u4ea4\u6362 state[2x] \u4e0e state[2x+1] \u4e24\u4e2a\u632f\u5e45，f(x)=0f(x)=0<\/span><\/span>f<\/span>(<\/span>x<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span><\/span> \u65f6\u4fdd\u6301\u4e0d\u53d8\u2014\u2014\u8fd9\u662f\u5bf9\u5b9a\u4e49 3.2 \u7684\u9010\u6bd4\u7279\u7cbe\u786e\u5b9e\u73b0，\u4e0d\u6d89\u53ca\u4efb\u4f55\u6d6e\u70b9\u8fd1\u4f3c，\u56e0\u6b64\u540e\u7eed\u6d4b\u5f97\u7684\u76f8\u4f4d\u56dekickback\u6548\u5e94\u662f\u4ee3\u6570\u7cbe\u786e\u7684，\u4e0d\u662f\u6570\u503c\u5de7\u5408\u3002<\/p>\n

\u5b9e\u73b0\u4e86\u56db\u7c7b Oracle：<\/p>\n