8 Puzzle
Andreas Wichert · 2023
The n -puzzle is a classical problem for modeling algorithms. For n -puzzle there are https://www.w3.org/1998/Math/MathML" display="inline"> n + 1 https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_1.tif "/> different objects: n cells and one empty cell. Each object can be coded by https://www.w3.org/1998/Math/MathML" display="inline"> ρ = ⌈ log 2 n + 1 ⌉ https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_2.tif "/> qubits and a configuration of https://www.w3.org/1998/Math/MathML" display="inline"> n + 1 https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_3.tif "/> objects can be represented by a register of https://www.w3.org/1998/Math/MathML" display="inline"> z := ρ ⋅ ( n + 1 ) https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_4.tif "/> qubits https://www.w3.org/1998/Math/MathML" display="inline"> | x ⟩ https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_5.tif "/> . The function https://www.w3.org/1998/Math/MathML" display="inline"> g ( x ) https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_6.tif "/> is represented a unitary operator T . T acts on the https://www.w3.org/1998/Math/MathML" display="inline"> z + 1 https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_7.tif "/> qubits with https://www.w3.org/1998/Math/MathML" display="inline"> x ∈ B z https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_8.tif "/> and https://www.w3.org/1998/Math/MathML" display="inline"> c ∈ B 1 https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_9.tif "/> https://www.w3.org/1998/Math/MathML" display="block"> T ⋅ | x ⟩ | c ⟩ = | x ⟩ | f ( x ) ⊕ c ⟩ . https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math10_10.tif "/>