grover

import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20qulacs%20import%20QuantumCircuit%2C%20QuantumState%0A%20%20%20%20from%20qulacs.gate%20import%20RZ%2C%20H%2C%20X%2C%20Z%2C%20to_matrix_gate%0A%20%20%20%20from%20qulacs.state%20import%20inner_product%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20H%2C%0A%20%20%20%20%20%20%20%20QuantumCircuit%2C%0A%20%20%20%20%20%20%20%20QuantumState%2C%0A%20%20%20%20%20%20%20%20RZ%2C%0A%20%20%20%20%20%20%20%20X%2C%0A%20%20%20%20%20%20%20%20Z%2C%0A%20%20%20%20%20%20%20%20inner_product%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20to_matrix_gate%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Grover%20%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%0A%0A%20%20%20%20Jupyter%20%2F%20Colab%20%E3%83%9E%E3%82%B8%E3%83%83%E3%82%AF%E3%82%92%E9%99%A4%E5%8E%BB%E3%81%97%E3%80%81%E9%87%8F%E5%AD%90%E7%8A%B6%E6%85%8B%E3%81%AE%E5%88%86%E5%B8%83%E3%82%92%E9%9D%99%E6%AD%A2%E7%94%BB%E3%81%A8%E3%81%97%E3%81%A6%E8%BF%BD%E3%81%88%E3%82%8B%E3%82%88%E3%81%86%E3%81%AB%E6%95%B4%E7%90%86%E3%81%97%E3%81%9F%E3%80%82%0A%20%20%20%20%E7%9B%AE%E6%A8%99%E7%8A%B6%E6%85%8B%E3%81%AF%20%24%7C11%5Cldots1%5Crangle%24%20%E3%81%A8%E3%81%99%E3%82%8B%E3%80%82%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20plt)%3A%0A%20%20%20%20def%20distribution_figure(state%2C%20nqubits%3A%20int%2C%20title%3A%20str)%3A%0A%20%20%20%20%20%20%20%20figure%2C%20axis%20%3D%20plt.subplots(figsize%3D(7%2C%203))%0A%20%20%20%20%20%20%20%20amplitudes%20%3D%20np.abs(state.get_vector())%0A%20%20%20%20%20%20%20%20axis.bar(range(2**nqubits)%2C%20amplitudes)%0A%20%20%20%20%20%20%20%20axis.set_xlabel(%22basis%20state%22)%0A%20%20%20%20%20%20%20%20axis.set_ylabel(%22%7Camplitude%7C%22)%0A%20%20%20%20%20%20%20%20axis.set_title(title)%0A%20%20%20%20%20%20%20%20return%20figure%0A%0A%20%20%20%20return%20(distribution_figure%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%E9%87%8F%E5%AD%90%E7%8A%B6%E6%85%8B%E3%82%92%E5%88%9D%E6%9C%9F%E5%8C%96%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(QuantumState%2C%20distribution_figure)%3A%0A%20%20%20%20nqubits%20%3D%205%0A%20%20%20%20zero_state%20%3D%20QuantumState(nqubits)%0A%20%20%20%20zero_state.set_zero_state()%0A%20%20%20%20distribution_figure(zero_state%2C%20nqubits%2C%20%22zero%20state%22)%0A%20%20%20%20return%20nqubits%2C%20zero_state%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Hadamard%20%E5%A4%89%E6%8F%9B%E3%81%A7%E4%B8%80%E6%A7%98%E7%8A%B6%E6%85%8B%E3%81%AB%E3%81%99%E3%82%8B%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(H%2C%20QuantumCircuit)%3A%0A%20%20%20%20def%20make_hadamard(nqubits%3A%20int)%3A%0A%20%20%20%20%20%20%20%20hadamard%20%3D%20QuantumCircuit(nqubits)%0A%20%20%20%20%20%20%20%20for%20qubit%20in%20range(nqubits)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20hadamard.add_gate(H(qubit))%0A%20%20%20%20%20%20%20%20return%20hadamard%0A%0A%20%20%20%20return%20(make_hadamard%2C)%0A%0A%0A%40app.cell%0Adef%20_(distribution_figure%2C%20make_hadamard%2C%20nqubits%2C%20zero_state)%3A%0A%20%20%20%20hadamard%20%3D%20make_hadamard(nqubits)%0A%20%20%20%20uniform_state%20%3D%20zero_state.copy()%0A%20%20%20%20hadamard.update_quantum_state(uniform_state)%0A%20%20%20%20distribution_figure(uniform_state%2C%20nqubits%2C%20%22uniform%20superposition%22)%0A%20%20%20%20return%20hadamard%2C%20uniform_state%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Oracle%20%E3%82%92%E4%BD%9C%E3%82%8B%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(QuantumCircuit%2C%20Z%2C%20to_matrix_gate)%3A%0A%20%20%20%20def%20make_oracle(nqubits%3A%20int)%3A%0A%20%20%20%20%20%20%20%20oracle%20%3D%20QuantumCircuit(nqubits)%0A%20%20%20%20%20%20%20%20controlled_z%20%3D%20to_matrix_gate(Z(nqubits%20-%201))%0A%20%20%20%20%20%20%20%20for%20qubit%20in%20range(nqubits%20-%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20controlled_z.add_control_qubit(qubit%2C%201)%0A%20%20%20%20%20%20%20%20oracle.add_gate(controlled_z)%0A%20%20%20%20%20%20%20%20return%20oracle%0A%0A%20%20%20%20return%20(make_oracle%2C)%0A%0A%0A%40app.cell%0Adef%20_(distribution_figure%2C%20make_oracle%2C%20nqubits%2C%20uniform_state)%3A%0A%20%20%20%20oracle%20%3D%20make_oracle(nqubits)%0A%20%20%20%20oracle_state%20%3D%20uniform_state.copy()%0A%20%20%20%20oracle.update_quantum_state(oracle_state)%0A%20%20%20%20distribution_figure(oracle_state%2C%20nqubits%2C%20%22after%20oracle%22)%0A%20%20%20%20return%20(oracle%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%E6%8B%A1%E6%95%A3%E5%A4%89%E6%8F%9B%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(H%2C%20QuantumCircuit%2C%20RZ%2C%20X%2C%20Z%2C%20np%2C%20to_matrix_gate)%3A%0A%20%20%20%20def%20make_diffusion(nqubits%3A%20int)%3A%0A%20%20%20%20%20%20%20%20diffusion%20%3D%20QuantumCircuit(nqubits)%0A%20%20%20%20%20%20%20%20for%20qubit%20in%20range(nqubits)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20diffusion.add_gate(H(qubit))%0A%20%20%20%20%20%20%20%20diffusion.add_gate(to_matrix_gate(RZ(nqubits%20-%201%2C%202%20*%20np.pi)))%0A%20%20%20%20%20%20%20%20diffusion.add_gate(X(nqubits%20-%201))%0A%20%20%20%20%20%20%20%20controlled_z%20%3D%20to_matrix_gate(Z(nqubits%20-%201))%0A%20%20%20%20%20%20%20%20for%20qubit%20in%20range(nqubits%20-%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20controlled_z.add_control_qubit(qubit%2C%200)%0A%20%20%20%20%20%20%20%20diffusion.add_gate(controlled_z)%0A%20%20%20%20%20%20%20%20diffusion.add_gate(X(nqubits%20-%201))%0A%20%20%20%20%20%20%20%20for%20qubit%20in%20range(nqubits)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20diffusion.add_gate(H(qubit))%0A%20%20%20%20%20%20%20%20return%20diffusion%0A%0A%20%20%20%20return%20(make_diffusion%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20QuantumState%2C%0A%20%20%20%20distribution_figure%2C%0A%20%20%20%20hadamard%2C%0A%20%20%20%20make_diffusion%2C%0A%20%20%20%20nqubits%2C%0A%20%20%20%20oracle%2C%0A)%3A%0A%20%20%20%20diffusion%20%3D%20make_diffusion(nqubits)%0A%20%20%20%20one_step_state%20%3D%20QuantumState(nqubits)%0A%20%20%20%20one_step_state.set_zero_state()%0A%20%20%20%20hadamard.update_quantum_state(one_step_state)%0A%20%20%20%20oracle.update_quantum_state(one_step_state)%0A%20%20%20%20diffusion.update_quantum_state(one_step_state)%0A%20%20%20%20distribution_figure(one_step_state%2C%20nqubits%2C%20%22after%20one%20Grover%20iteration%22)%0A%20%20%20%20return%20(diffusion%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%E5%8F%8D%E5%BE%A9%E3%81%A7%E6%AD%A3%E7%AD%94%E7%A2%BA%E7%8E%87%E3%81%8C%E4%B8%8A%E3%81%8C%E3%82%8B%E6%A7%98%E5%AD%90%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20QuantumState%2C%0A%20%20%20%20diffusion%2C%0A%20%20%20%20hadamard%2C%0A%20%20%20%20inner_product%2C%0A%20%20%20%20np%2C%0A%20%20%20%20nqubits%2C%0A%20%20%20%20oracle%2C%0A%20%20%20%20plt%2C%0A)%3A%0A%20%20%20%20target_state%20%3D%20QuantumState(nqubits)%0A%20%20%20%20target_state.set_computational_basis(2**nqubits%20-%201)%0A%20%20%20%20state_iter%20%3D%20QuantumState(nqubits)%0A%20%20%20%20state_iter.set_zero_state()%0A%20%20%20%20hadamard.update_quantum_state(state_iter)%0A%0A%20%20%20%20probabilities%20%3D%20%5B%5D%0A%20%20%20%20snapshots%20%3D%20%5B%5D%0A%20%20%20%20for%20_iteration%20in%20range(4)%3A%0A%20%20%20%20%20%20%20%20oracle.update_quantum_state(state_iter)%0A%20%20%20%20%20%20%20%20diffusion.update_quantum_state(state_iter)%0A%20%20%20%20%20%20%20%20probabilities.append(np.linalg.norm(inner_product(state_iter%2C%20target_state)))%0A%20%20%20%20%20%20%20%20snapshots.append(np.abs(state_iter.get_vector()))%0A%0A%20%20%20%20figure_iter%2C%20axes_iter%20%3D%20plt.subplots(2%2C%202%2C%20figsize%3D(12%2C%206)%2C%20sharey%3DTrue)%0A%20%20%20%20for%20axis_iter%2C%20iteration_label%2C%20amplitudes%2C%20probability%20in%20zip(axes_iter.ravel()%2C%20range(1%2C%205)%2C%20snapshots%2C%20probabilities%2C%20strict%3DTrue)%3A%0A%20%20%20%20%20%20%20%20axis_iter.bar(range(2**nqubits)%2C%20amplitudes)%0A%20%20%20%20%20%20%20%20axis_iter.set_title(f%22k%3D%7Biteration_label%7D%2C%20success%3D%7Bprobability%3A.3f%7D%22)%0A%20%20%20%20figure_iter.tight_layout()%0A%20%20%20%20figure_iter%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%2010%20%E9%87%8F%E5%AD%90%E3%83%93%E3%83%83%E3%83%88%E3%81%A7%E3%81%AE%E5%8F%8D%E5%BE%A9%E5%9B%9E%E6%95%B0%E4%BE%9D%E5%AD%98%E6%80%A7%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20QuantumState%2C%0A%20%20%20%20inner_product%2C%0A%20%20%20%20make_diffusion%2C%0A%20%20%20%20make_hadamard%2C%0A%20%20%20%20make_oracle%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A)%3A%0A%20%20%20%20nqubits_large%20%3D%2010%0A%20%20%20%20target_state_large%20%3D%20QuantumState(nqubits_large)%0A%20%20%20%20target_state_large.set_computational_basis(2**nqubits_large%20-%201)%0A%20%20%20%20hadamard_large%20%3D%20make_hadamard(nqubits_large)%0A%20%20%20%20oracle_large%20%3D%20make_oracle(nqubits_large)%0A%20%20%20%20diffusion_large%20%3D%20make_diffusion(nqubits_large)%0A%20%20%20%20state_large%20%3D%20QuantumState(nqubits_large)%0A%20%20%20%20state_large.set_zero_state()%0A%20%20%20%20hadamard_large.update_quantum_state(state_large)%0A%0A%20%20%20%20success_curve%20%3D%20%5B%5D%0A%20%20%20%20for%20_iteration%20in%20range(30)%3A%0A%20%20%20%20%20%20%20%20oracle_large.update_quantum_state(state_large)%0A%20%20%20%20%20%20%20%20diffusion_large.update_quantum_state(state_large)%0A%20%20%20%20%20%20%20%20success_curve.append(np.linalg.norm(inner_product(state_large%2C%20target_state_large)))%0A%0A%20%20%20%20max_iteration%20%3D%20int(np.argmax(success_curve))%20%2B%201%0A%20%20%20%20print(f%22maximal%20probability%20%7Bsuccess_curve%5Bmax_iteration%20-%201%5D%3A.5e%7D%20is%20obtained%20at%20k%20%3D%20%7Bmax_iteration%7D%22)%0A%20%20%20%20figure_curve%2C%20axis_curve%20%3D%20plt.subplots(figsize%3D(7%2C%204))%0A%20%20%20%20axis_curve.plot(np.arange(1%2C%2031)%2C%20success_curve%2C%20%22o-%22)%0A%20%20%20%20axis_curve.set_xlabel(%22iteration%22)%0A%20%20%20%20axis_curve.set_ylabel(%22success%20probability%22)%0A%20%20%20%20axis_curve.set_title(%2210-qubit%20Grover%20search%22)%0A%20%20%20%20figure_curve%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%E9%87%8F%E5%AD%90%E3%83%93%E3%83%83%E3%83%88%E6%95%B0%E3%81%A8%E6%9C%80%E9%81%A9%E5%8F%8D%E5%BE%A9%E5%9B%9E%E6%95%B0%E3%81%AE%E9%96%A2%E4%BF%82%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20QuantumState%2C%0A%20%20%20%20inner_product%2C%0A%20%20%20%20make_diffusion%2C%0A%20%20%20%20make_hadamard%2C%0A%20%20%20%20make_oracle%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A)%3A%0A%20%20%20%20scaling_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20nqubits_scaling%20in%20range(6%2C%2017%2C%202)%3A%0A%20%20%20%20%20%20%20%20target_state_scaling%20%3D%20QuantumState(nqubits_scaling)%0A%20%20%20%20%20%20%20%20target_state_scaling.set_computational_basis(2**nqubits_scaling%20-%201)%0A%20%20%20%20%20%20%20%20hadamard_scaling%20%3D%20make_hadamard(nqubits_scaling)%0A%20%20%20%20%20%20%20%20oracle_scaling%20%3D%20make_oracle(nqubits_scaling)%0A%20%20%20%20%20%20%20%20diffusion_scaling%20%3D%20make_diffusion(nqubits_scaling)%0A%20%20%20%20%20%20%20%20state_scaling%20%3D%20QuantumState(nqubits_scaling)%0A%20%20%20%20%20%20%20%20state_scaling.set_zero_state()%0A%20%20%20%20%20%20%20%20hadamard_scaling.update_quantum_state(state_scaling)%0A%0A%20%20%20%20%20%20%20%20best_probability%20%3D%200.0%0A%20%20%20%20%20%20%20%20best_iteration%20%3D%200%0A%20%20%20%20%20%20%20%20for%20_iteration_count%20in%20range(1%2C%201001)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20oracle_scaling.update_quantum_state(state_scaling)%0A%20%20%20%20%20%20%20%20%20%20%20%20diffusion_scaling.update_quantum_state(state_scaling)%0A%20%20%20%20%20%20%20%20%20%20%20%20success_probability%20%3D%20np.linalg.norm(inner_product(state_scaling%2C%20target_state_scaling))%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20success_probability%20%3E%3D%20best_probability%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_probability%20%3D%20success_probability%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_iteration%20%3D%20_iteration_count%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20scaling_rows.append((nqubits_scaling%2C%20best_iteration%2C%20best_probability))%0A%20%20%20%20%20%20%20%20print(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22nqubits%3D%7Bnqubits_scaling%7D%2C%20num_iter%3D%7Bbest_iteration%7D%2C%20suc_prob%3D%7Bbest_probability%3A.5e%7D%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20scaling_array%20%3D%20np.array(scaling_rows)%0A%20%20%20%20figure_scale%2C%20axis_scale%20%3D%20plt.subplots(figsize%3D(7%2C%204))%0A%20%20%20%20axis_scale.semilogy(scaling_array%5B%3A%2C%200%5D%2C%20scaling_array%5B%3A%2C%201%5D%2C%20%22o-%22%2C%20label%3D%22experiment%22)%0A%20%20%20%20axis_scale.semilogy(scaling_array%5B%3A%2C%200%5D%2C%200.05%20*%202%20**%20scaling_array%5B%3A%2C%200%5D%2C%20%22-%22%2C%20label%3D%22%24%5C%5Cpropto%20N%3D2%5En%24%22)%0A%20%20%20%20axis_scale.semilogy(scaling_array%5B%3A%2C%200%5D%2C%202%20**%20(0.5%20*%20scaling_array%5B%3A%2C%200%5D)%2C%20%22-%22%2C%20label%3D%22%24%5C%5Cpropto%20%5C%5Csqrt%7BN%7D%3D2%5E%7Bn%2F2%7D%24%22)%0A%20%20%20%20axis_scale.set_xlabel(%22n%2C%20%23%20of%20qubits%22)%0A%20%20%20%20axis_scale.set_ylabel(%22k%2C%20%23%20of%20iterations%22)%0A%20%20%20%20axis_scale.legend(fontsize%3D10)%0A%20%20%20%20figure_scale%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A