Grover's Algorithm - Revision history

Mol: /* Application: Lights Out */

2020-11-29T09:55:21Z

Application: Lights Out

← Older revision		Revision as of 12:55, 29 November 2020
Line 178:		Line 178:
	print( final_score )		print( final_score )
	</syntaxhighlight>		</syntaxhighlight>

			The example above is very low and inefficient. It can be sped up.

	=== References ===		=== References ===

2020-11-28T10:50:44Z

Application: Lights Out

← Older revision		Revision as of 13:50, 28 November 2020
Line 16:		Line 16:

	== Application: Lights Out ==		== Application: Lights Out ==

			[[File:LightsOut.png\|thumb]]

	We solve the <math>3\times3</math> tiling game using superposition (instead of Gaussian elimination). The algorithm finds the N-qubit for which the initial state becomes zero.		We solve the <math>3\times3</math> tiling game using superposition (instead of Gaussian elimination). The algorithm finds the N-qubit for which the initial state becomes zero.

2020-11-27T13:14:02Z

References

← Older revision		Revision as of 16:14, 27 November 2020
Line 184:		Line 184:

	https://gaming.stackexchange.com/questions/11123/strategy-for-solving-lights-out-puzzle		https://gaming.stackexchange.com/questions/11123/strategy-for-solving-lights-out-puzzle

			https://github.com/qiskit-community/IBMQuantumChallenge2020/blob/main/hints/hint_2a_nb/hint_2a_ex.ipynb

	== References ==		== References ==

2020-11-27T13:08:42Z

Application: Lights Out

← Older revision		Revision as of 16:08, 27 November 2020
Line 162:		Line 162:
	qc.measure(flip,result)		qc.measure(flip,result)
	qc.barrier()		qc.barrier()
	# Make the ~~Out put~~ order the same as the input.		# Make the output order the same as the input.
	qc = qc.reverse_bits()		qc = qc.reverse_bits()

2020-11-27T12:46:38Z

Application: Lights Out

← Older revision		Revision as of 15:46, 27 November 2020
Line 30:		Line 30:
	\|}		\|}

	Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus the toggle mapping is:		Second, we need a function that flips the lights: By pressing 0 the light in cells {0, 1, 3} will toggle. Thus the toggle mapping is:
	* 0 -> {0, 1, 3}		* 0 -> {0, 1, 3}
	* 1 -> {0, 1, 2, 4}		* 1 -> {0, 1, 2, 4}

2020-11-27T12:46:19Z

Application: Lights Out

← Older revision		Revision as of 15:46, 27 November 2020
Line 43:		Line 43:
	The diffusion (Amplification) part is the most difficult.		The diffusion (Amplification) part is the most difficult.

	Solution space is <math>2^9=512</math>, the optimal number of iteration is about <math>\frac{\pi}{4} \sqrt{2^9} - \frac{1}{2} \approx 17.3 \approx 17<math>.		Solution space is <math>2^9=512</math>, the optimal number of iteration is about <math>\frac{\pi}{4} \sqrt{2^9} - \frac{1}{2} \approx 17.3 \approx 17</math>.

	<syntaxhighlight>		<syntaxhighlight>

2020-11-27T12:45:49Z

Application: Lights Out

← Older revision		Revision as of 15:45, 27 November 2020
Line 74:		Line 74:
	qc.h(flip[:])		qc.h(flip[:])

	qc.x(oracle[0])		qc.x(oracle[0])
	qc.h(oracle[0])		qc.h(oracle[0]) #Hadamard superposition



	# Subroutine for oracle		# Subroutine for oracle
	~~# Calculate what the light state will be after pressing each solution candidate.~~
	def flip_tile(qc,flip,tile):		def flip_tile(qc,flip,tile):
	qc.cx(flip[0], tile[0])		qc.cx(flip[0], tile[0])
Line 135:		Line 132:
	qc.barrier()		qc.barrier()

	~~#Solution space is 2^9=512, the optimal number of iteration is about $\frac{\pi}{4} \sqrt{2^9} - \frac{1}{2} \risingdotseq 17.3$, so try it $3$ times.~~

	~~# the number of iteration is 3~~
	for i in range(17):		for i in range(17):
	# oracle		# oracle
	flip_tile(qc,flip,tile)		flip_tile(qc,flip,tile)

	qc.barrier()		qc.barrier()

	all_zero(qc, tile)		all_zero(qc, tile)

	qc.barrier()		qc.barrier()

	# U^dagger of flip_tile ~~function is flip_tile itself~~.		# U^dagger of flip_tile.
	flip_tile(qc,flip,tile)		flip_tile(qc,flip,tile)

	qc.barrier()		qc.barrier()

Line 162:		Line 153:
	qc.h(flip)		qc.h(flip)
	qc.barrier()		qc.barrier()



	# Uncompute		# Uncompute
Line 180:		Line 169:

	backend = Aer.get_backend('statevector_simulator')		backend = Aer.get_backend('statevector_simulator')

	job = execute(qc,backend)		job = execute(qc,backend)

	result = job.result()		result = job.result()

	count = result.get_counts()		count = result.get_counts()
	score_sorted = sorted(count.items(), key=lambda x:x[1], reverse=True)		score_sorted = sorted(count.items(), key=lambda x:x[1], reverse=True)

2020-11-27T12:42:24Z

Application: Lights Out

2020-11-27T09:39:17Z

Application: Lights Out

← Older revision		Revision as of 12:39, 27 November 2020
Line 29:		Line 29:

	Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus the toggle mapping is:		Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus the toggle mapping is:
	* 0 -> {1,3}		* 0 -> {0, 1, 3}
	* 1 -> {0, 2, 4}		* 1 -> {0, 1, 2, 4}
	* 2 -> {1, 5}		* 2 -> {1, 2, 5}
	* 3 -> {0, 4, 6}		* 3 -> {0, 3, 4, 6}
	* 4 -> {1, 3, 5, 7}		* 4 -> {1, 3, 4, 5, 7}
	* 5 -> {2, 4, 8}		* 5 -> {2, 4, 5, 8}
	* 6 -> {3, 7}		* 6 -> {3, 6, 7}
	* 7 -> {4, 6, 8}		* 7 -> {4, 6, 7, 8}
	* 8 -> {5, 7}		* 8 -> {5, 7, 8}

2020-11-27T09:12:01Z

Application: Lights Out

← Older revision		Revision as of 12:12, 27 November 2020
Line 28:		Line 28:
	\|}		\|}

	Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus ~~we will have~~:		Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus the toggle mapping is:
	*		* 0 -> {1,3}
			* 1 -> {0, 2, 4}
			* 2 -> {1, 5}
			* 3 -> {0, 4, 6}
			* 4 -> {1, 3, 5, 7}
			* 5 -> {2, 4, 8}
			* 6 -> {3, 7}
			* 7 -> {4, 6, 8}
			* 8 -> {5, 7}