Quantum counting algorithm - Revision history

A40585 at 00:54, 22 January 2025

2025-01-22T00:54:39Z

← Previous revision		Revision as of 00:54, 22 January 2025
Line 1:		Line 1:
	{{Short description\|Quantum algorithm for counting solutions to search problems}}		{{Short description\|Quantum algorithm for counting solutions to search problems}}
	'''Quantum counting algorithm''' is a [[quantum algorithm]] for efficiently counting the number of solutions for a given search problem.		The '''Quantum counting algorithm''' is a [[quantum algorithm]] for efficiently counting the number of solutions for a given search problem.
	The algorithm is based on the [[quantum phase estimation algorithm]] and on [[Grover's algorithm\|Grover's search algorithm]].		The algorithm is based on the [[quantum phase estimation algorithm]] and on [[Grover's algorithm\|Grover's search algorithm]].

	Counting problems are common in diverse fields such as statistical estimation, statistical physics, networking, etc.		Counting problems are common in diverse fields such as statistical estimation, statistical physics, networking, etc. As for [[quantum computing]], the ability to perform quantum counting efficiently is needed in order to use Grover's search algorithm (because running Grover's search algorithm requires knowing how many solutions exist). Moreover, this algorithm solves the quantum existence problem (namely, deciding whether ''any'' solution exists) as a special case.
	As for [[quantum computing]], the ability to perform quantum counting efficiently is needed in order to use Grover's search algorithm (because running Grover's search algorithm requires knowing how many solutions exist). Moreover, this algorithm solves the quantum existence problem (namely, deciding whether ''any'' solution exists) as a special case.

	The algorithm was devised by [[Gilles Brassard]], Peter Høyer and Alain Tapp in 1998.		The algorithm was devised by [[Gilles Brassard]], Peter Høyer and Alain Tapp in 1998.

A40585: citation fix

2024-10-16T20:25:37Z

citation fix

← Previous revision		Revision as of 20:25, 16 October 2024
Line 15:		Line 15:
	In other words, <math>f</math> is the [[indicator function]] of <math>B</math>.		In other words, <math>f</math> is the [[indicator function]] of <math>B</math>.

	Calculate the number of solutions <math> M = \left\vert f^{-1}(1) \right\vert = \vert B \vert</math>.<ref name = brassard>{{~~cite~~ ~~book~~\|title=Automata, Languages and Programming\|~~date~~=~~July~~ ~~13–17,~~ ~~1998~~\|~~publisher~~=~~Springer~~ ~~Berlin Heidelberg~~\|~~location~~=~~ICALP'98~~ ~~Aalborg,~~ ~~Denmark~~\|~~isbn~~=~~978~~-3-~~540~~-~~64781-2~~\|~~pages~~=~~820–831~~\|~~edition~~=~~25th~~ ~~International~~ ~~Colloquium~~\|arxiv=quant-ph/9805082\|doi=10.1007/~~BFb0055105\| last1 = Brassard~~ \| ~~first1~~ =~~Gilles~~ \| last2 = ~~Hoyer~~ \| first2 = Peter \| last3 = Tapp \| first3 =Alain\|~~s2cid~~=~~14147978~~}}</ref>		Calculate the number of solutions <math> M = \left\vert f^{-1}(1) \right\vert = \vert B \vert</math>.<ref name="brassard">{{Citation \|last=Brassard \|first=Gilles \|title=Quantum counting \|date=1998 \|work=Automata, Languages and Programming \|volume=1443 \|pages=820–831 \|editor-last=Larsen \|editor-first=Kim G. \|url=http://link.springer.com/10.1007/BFb0055105 \|access-date=2024-10-16 \|place=Berlin, Heidelberg \|publisher=Springer Berlin Heidelberg \|arxiv=quant-ph/9805082 \|doi=10.1007/bfb0055105 \|isbn=978-3-540-64781-2 \|last2=HØyer \|first2=Peter \|last3=Tapp \|first3=Alain \|editor2-last=Skyum \|editor2-first=Sven \|editor3-last=Winskel \|editor3-first=Glynn}}</ref>

	=== Classical solution ===		=== Classical solution ===

Fawly: Undid revision 1227038056 by Orsgaba (talk) ; WP:LINKSPAM

2024-06-18T06:56:41Z

Undid revision 1227038056 by Orsgaba (talk) ; WP:LINKSPAM

← Previous revision		Revision as of 06:56, 18 June 2024
Line 114:		Line 114:

	{{Reflist}}		{{Reflist}}

	== External links ==
	* [https://short.classiq.io/quantum_counting Implementation of the Quantum counting algorithm with Classiq]


	{{Quantum information}}		{{Quantum information}}

David Radcliffe: Removed math tag from subsection title because it produced strange output in the table of contents

2024-06-03T18:07:35Z

Removed math tag from subsection title because it produced strange output in the table of contents

← Previous revision		Revision as of 18:07, 3 June 2024
Line 64:		Line 64:
	From the [[Rotation matrix#Properties of a rotation matrix\|properties of rotation matrices]] we know that <math>G</math> is a [[unitary matrix]] with the two [[eigenvalues]] <math>e^{\pm i \theta}</math>.<ref name= nielchuan />{{rp\|253}}		From the [[Rotation matrix#Properties of a rotation matrix\|properties of rotation matrices]] we know that <math>G</math> is a [[unitary matrix]] with the two [[eigenvalues]] <math>e^{\pm i \theta}</math>.<ref name= nielchuan />{{rp\|253}}

	===Estimating the value of ~~<math>\theta</math>~~===		===Estimating the value of θ===
	From here onwards, we follow the [[quantum phase estimation algorithm]] scheme: we apply [[Quantum gate#Controlled gates\|controlled Grover]] operations followed by inverse [[quantum Fourier transform]]; and according to the [[Quantum phase estimation algorithm#Analysis\|analysis]], we will find the best <math>p</math>-bit approximation to the [[real number]] <math>\theta</math> (belonging to the eigenvalues <math>e^{\pm i \theta}</math> of the Grover operator) with probability higher than <math>\frac{4}{\pi^2}</math>.<ref name = ekert>{{cite journal\|last1=Cleve\|first1=R.\|last2=Ekert\|first2=A.\|last3=Macchiavello\|first3=C.\|last4=Mosca\|first4=M.\|title=Quantum algorithms revisited\|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences\|date=8 January 1998\|volume=454\|issue=1969\|pages=339–354\|arxiv=quant-ph/9708016\|doi=10.1098/rspa.1998.0164\|bibcode=1998RSPSA.454..339C\|s2cid=16128238}}</ref>{{rp\|348}}<ref name = benet />{{rp\|157}}		From here onwards, we follow the [[quantum phase estimation algorithm]] scheme: we apply [[Quantum gate#Controlled gates\|controlled Grover]] operations followed by inverse [[quantum Fourier transform]]; and according to the [[Quantum phase estimation algorithm#Analysis\|analysis]], we will find the best <math>p</math>-bit approximation to the [[real number]] <math>\theta</math> (belonging to the eigenvalues <math>e^{\pm i \theta}</math> of the Grover operator) with probability higher than <math>\frac{4}{\pi^2}</math>.<ref name = ekert>{{cite journal\|last1=Cleve\|first1=R.\|last2=Ekert\|first2=A.\|last3=Macchiavello\|first3=C.\|last4=Mosca\|first4=M.\|title=Quantum algorithms revisited\|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences\|date=8 January 1998\|volume=454\|issue=1969\|pages=339–354\|arxiv=quant-ph/9708016\|doi=10.1098/rspa.1998.0164\|bibcode=1998RSPSA.454..339C\|s2cid=16128238}}</ref>{{rp\|348}}<ref name = benet />{{rp\|157}}

Orsgaba: Added an external link for the algorithm's implementation

2024-06-03T08:52:06Z

Added an external link for the algorithm's implementation

← Previous revision		Revision as of 08:52, 3 June 2024
Line 114:		Line 114:

	{{Reflist}}		{{Reflist}}

			== External links ==
			* [https://short.classiq.io/quantum_counting Implementation of the Quantum counting algorithm with Classiq]


	{{Quantum information}}		{{Quantum information}}

Deep Gabriel: Adding local short description: "Quantum algorithm for counting solutions to search problems", overriding Wikidata description "quantum algorithm for efficiently counting the number of solutions for a given search problem"

2023-05-23T18:25:36Z

Adding local short description: "Quantum algorithm for counting solutions to search problems", overriding Wikidata description "quantum algorithm for efficiently counting the number of solutions for a given search problem"

← Previous revision		Revision as of 18:25, 23 May 2023
Line 1:		Line 1:
			{{Short description\|Quantum algorithm for counting solutions to search problems}}
	'''Quantum counting algorithm''' is a [[quantum algorithm]] for efficiently counting the number of solutions for a given search problem.		'''Quantum counting algorithm''' is a [[quantum algorithm]] for efficiently counting the number of solutions for a given search problem.
	The algorithm is based on the [[quantum phase estimation algorithm]] and on [[Grover's algorithm\|Grover's search algorithm]].		The algorithm is based on the [[quantum phase estimation algorithm]] and on [[Grover's algorithm\|Grover's search algorithm]].

Hannes.nutzernameistbereitsvergeben: The log^3 that was previously here is wrong. There is no exponential stuff involved. The given source states: "computational complexity we can state that the quantum existence tester saves n/2 qbits and 3 qbits in classical accuracy and quantum uncertainty compared to the quantum counting circuit"

2022-11-09T15:35:07Z

The log^3 that was previously here is wrong. There is no exponential stuff involved. The given source states: "computational complexity we can state that the quantum existence tester saves n/2 qbits and 3 qbits in classical accuracy and quantum uncertainty compared to the quantum counting circuit"

← Previous revision		Revision as of 15:35, 9 November 2022
Line 98:		Line 98:
	Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|last1=Imre\|first1=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}		Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|last1=Imre\|first1=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}

	A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead~~, i.e., to reduce its computational complexity from <math> \log^3(N) </math> to <math> \log^3(\sqrt{N}) </math>~~.<ref name = imres1 />{{rp\|148}}		A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead.<ref name = imres1 />{{rp\|148}}

	If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of <math>\theta</math>, but will suffice to determine whether <math>M</math> equals zero or not.<ref name = nielchuan />{{rp\|263}}		If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of <math>\theta</math>, but will suffice to determine whether <math>M</math> equals zero or not.<ref name = nielchuan />{{rp\|263}}

Citation bot: Alter: journal. Add: doi, pages, s2cid, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 315/409

2022-04-06T00:09:26Z

Alter: journal. Add: doi, pages, s2cid, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 315/409

← Previous revision		Revision as of 00:09, 6 April 2022
Line 14:		Line 14:
	In other words, <math>f</math> is the [[indicator function]] of <math>B</math>.		In other words, <math>f</math> is the [[indicator function]] of <math>B</math>.

	Calculate the number of solutions <math> M = \left\vert f^{-1}(1) \right\vert = \vert B \vert</math>.<ref name = brassard>{{cite book\|title=Automata, Languages and Programming\|date=July 13–17, 1998\|publisher=Springer Berlin Heidelberg\|location=ICALP'98 Aalborg, Denmark\|isbn=978-3-540-64781-2\|pages=820–831\|edition=25th International Colloquium\|arxiv=quant-ph/9805082\|doi=10.1007/BFb0055105\| last1 = Brassard \| first1 =Gilles \| last2 = Hoyer \| first2 = Peter \| last3 = Tapp \| first3 =Alain}}</ref>		Calculate the number of solutions <math> M = \left\vert f^{-1}(1) \right\vert = \vert B \vert</math>.<ref name = brassard>{{cite book\|title=Automata, Languages and Programming\|date=July 13–17, 1998\|publisher=Springer Berlin Heidelberg\|location=ICALP'98 Aalborg, Denmark\|isbn=978-3-540-64781-2\|pages=820–831\|edition=25th International Colloquium\|arxiv=quant-ph/9805082\|doi=10.1007/BFb0055105\| last1 = Brassard \| first1 =Gilles \| last2 = Hoyer \| first2 = Peter \| last3 = Tapp \| first3 =Alain\|s2cid=14147978}}</ref>

	=== Classical solution ===		=== Classical solution ===
Line 64:		Line 64:

	===Estimating the value of <math>\theta</math>===		===Estimating the value of <math>\theta</math>===
	From here onwards, we follow the [[quantum phase estimation algorithm]] scheme: we apply [[Quantum gate#Controlled gates\|controlled Grover]] operations followed by inverse [[quantum Fourier transform]]; and according to the [[Quantum phase estimation algorithm#Analysis\|analysis]], we will find the best <math>p</math>-bit approximation to the [[real number]] <math>\theta</math> (belonging to the eigenvalues <math>e^{\pm i \theta}</math> of the Grover operator) with probability higher than <math>\frac{4}{\pi^2}</math>.<ref name = ekert>{{cite journal\|last1=Cleve\|first1=R.\|last2=Ekert\|first2=A.\|last3=Macchiavello\|first3=C.\|last4=Mosca\|first4=M.\|title=Quantum algorithms revisited\|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences\|date=8 January 1998\|volume=454\|issue=1969\|arxiv=quant-ph/9708016\|doi=10.1098/rspa.1998.0164\|bibcode=1998RSPSA.454..339C}}</ref>{{rp\|348}}<ref name = benet />{{rp\|157}}		From here onwards, we follow the [[quantum phase estimation algorithm]] scheme: we apply [[Quantum gate#Controlled gates\|controlled Grover]] operations followed by inverse [[quantum Fourier transform]]; and according to the [[Quantum phase estimation algorithm#Analysis\|analysis]], we will find the best <math>p</math>-bit approximation to the [[real number]] <math>\theta</math> (belonging to the eigenvalues <math>e^{\pm i \theta}</math> of the Grover operator) with probability higher than <math>\frac{4}{\pi^2}</math>.<ref name = ekert>{{cite journal\|last1=Cleve\|first1=R.\|last2=Ekert\|first2=A.\|last3=Macchiavello\|first3=C.\|last4=Mosca\|first4=M.\|title=Quantum algorithms revisited\|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences\|date=8 January 1998\|volume=454\|issue=1969\|pages=339–354\|arxiv=quant-ph/9708016\|doi=10.1098/rspa.1998.0164\|bibcode=1998RSPSA.454..339C\|s2cid=16128238}}</ref>{{rp\|348}}<ref name = benet />{{rp\|157}}

	Note that the second register is actually in a [[quantum superposition\|superposition]] of the [[eigenvectors]] of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate <math>\theta</math>, and with some probability, we approximate <math>2\pi - \theta</math>; those two approximations are equivalent.<ref name = nielchuan />{{rp\|224–225}}		Note that the second register is actually in a [[quantum superposition\|superposition]] of the [[eigenvectors]] of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate <math>\theta</math>, and with some probability, we approximate <math>2\pi - \theta</math>; those two approximations are equivalent.<ref name = nielchuan />{{rp\|224–225}}
Line 96:		Line 96:

	===Quantum existence problem===		===Quantum existence problem===
	Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|~~last~~=Imre\|~~first~~=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}		Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|last1=Imre\|first1=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}

	A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead, i.e., to reduce its computational complexity from <math> \log^3(N) </math> to <math> \log^3(\sqrt{N}) </math>.<ref name = imres1 />{{rp\|148}}		A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead, i.e., to reduce its computational complexity from <math> \log^3(N) </math> to <math> \log^3(\sqrt{N}) </math>.<ref name = imres1 />{{rp\|148}}
Line 103:		Line 103:

	===Quantum relation testing problem===		===Quantum relation testing problem===
	Quantum relation testing <math> QRT(value,relation)</math>. is an extension of quantum existence testing, it decides whether at least one entry can be found in the data base which fulfils the relation to a certain reference value. <ref name=imres2>{{Cite journal\| ~~last~~=Elgaily \|~~first~~=Sara\|last2=Imre\|first2=Sandor\|title=Constrained Quantum Optimization for Resource Distribution Management\|journal = ~~INTERNATIONAL~~ ~~JOURNAL~~ OF ~~ADVANCED~~ ~~COMPUTER~~ ~~SCIENCE~~ ~~AND~~ ~~APPLICATIONS~~\|date=2021\|volume=12\|issue=8}}</ref> E.g. <math> QRT(5,>)</math> gives back YES if the data base contains any value larger than 5 else it returns NO. Quantum relation testing combined with classical logarithmic search forms an efficient quantum min/max searching algorithm. <ref name = imres1 />{{rp\|152}} <ref name=imres3>{{Cite journal\|last=Imre\|first=Sandor\|title=Quantum Existence Testing and its Application for Finding Extreme Values in Unsorted Databases\|journal = IEEE ~~TRANSACTIONS~~ ON ~~COMPUTERS~~\|date=2007\|volume=56\|issue=5}}</ref>		Quantum relation testing <math> QRT(value,relation)</math>. is an extension of quantum existence testing, it decides whether at least one entry can be found in the data base which fulfils the relation to a certain reference value. <ref name=imres2>{{Cite journal\| last1=Elgaily \|first1=Sara\|last2=Imre\|first2=Sandor\|title=Constrained Quantum Optimization for Resource Distribution Management\|journal = International Journal of Advanced Computer Science and Applications\|date=2021\|volume=12\|issue=8}}</ref> E.g. <math> QRT(5,>)</math> gives back YES if the data base contains any value larger than 5 else it returns NO. Quantum relation testing combined with classical logarithmic search forms an efficient quantum min/max searching algorithm. <ref name = imres1 />{{rp\|152}} <ref name=imres3>{{Cite journal\|last=Imre\|first=Sandor\|title=Quantum Existence Testing and its Application for Finding Extreme Values in Unsorted Databases\|journal = IEEE Transactions on Computers\|date=2007\|volume=56\|issue=5\|pages=706–710\|doi=10.1109/TC.2007.1032\|s2cid=29588344}}</ref>

	== See also ==		== See also ==

ImreSandor69 at 13:07, 22 March 2022

2022-03-22T13:07:33Z

← Previous revision		Revision as of 13:07, 22 March 2022
Line 96:		Line 96:

	===Quantum existence problem===		===Quantum existence problem===
	Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.		Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|last=Imre\|first=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}
⚫	A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>.

		⚫	A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead, i.e., to reduce its computational complexity from <math> \log^3(N) </math> to <math> \log^3(\sqrt{N}) </math>.<ref name = imres1 />{{rp\|148}}
⚫	~~Using~~ a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of <math>\theta</math>, but will suffice to determine whether <math>M</math> equals zero or not.<ref name = nielchuan />{{rp\|263}}

		⚫	If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of <math>\theta</math>, but will suffice to determine whether <math>M</math> equals zero or not.<ref name = nielchuan />{{rp\|263}}

			===Quantum relation testing problem===
			Quantum relation testing <math> QRT(value,relation)</math>. is an extension of quantum existence testing, it decides whether at least one entry can be found in the data base which fulfils the relation to a certain reference value. <ref name=imres2>{{Cite journal\| last=Elgaily \|first=Sara\|last2=Imre\|first2=Sandor\|title=Constrained Quantum Optimization for Resource Distribution Management\|journal = INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS\|date=2021\|volume=12\|issue=8}}</ref> E.g. <math> QRT(5,>)</math> gives back YES if the data base contains any value larger than 5 else it returns NO. Quantum relation testing combined with classical logarithmic search forms an efficient quantum min/max searching algorithm. <ref name = imres1 />{{rp\|152}} <ref name=imres3>{{Cite journal\|last=Imre\|first=Sandor\|title=Quantum Existence Testing and its Application for Finding Extreme Values in Unsorted Databases\|journal = IEEE TRANSACTIONS ON COMPUTERS\|date=2007\|volume=56\|issue=5}}</ref>

	== See also ==		== See also ==
Line 107:		Line 111:

	== References ==		== References ==

	{{Reflist}}		{{Reflist}}

ReyHahn: /* Estimating the value of \theta */ uppercase

2021-05-30T10:20:55Z

Estimating the value of \theta: uppercase

← Previous revision		Revision as of 10:20, 30 May 2021
Line 64:		Line 64:

	===Estimating the value of <math>\theta</math>===		===Estimating the value of <math>\theta</math>===
	From here onwards, we follow the [[quantum phase estimation algorithm]] scheme: we apply [[Quantum gate#Controlled gates\|controlled Grover]] operations followed by inverse [[~~Quantum~~ Fourier ~~transform\|quantum fourier~~ transform]]; and according to the [[Quantum phase estimation algorithm#Analysis\|analysis]], we will find the best <math>p</math>-bit approximation to the [[real number]] <math>\theta</math> (belonging to the eigenvalues <math>e^{\pm i \theta}</math> of the Grover operator) with probability higher than <math>\frac{4}{\pi^2}</math>.<ref name = ekert>{{cite journal\|last1=Cleve\|first1=R.\|last2=Ekert\|first2=A.\|last3=Macchiavello\|first3=C.\|last4=Mosca\|first4=M.\|title=Quantum algorithms revisited\|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences\|date=8 January 1998\|volume=454\|issue=1969\|arxiv=quant-ph/9708016\|doi=10.1098/rspa.1998.0164\|bibcode=1998RSPSA.454..339C}}</ref>{{rp\|348}}<ref name = benet />{{rp\|157}}		From here onwards, we follow the [[quantum phase estimation algorithm]] scheme: we apply [[Quantum gate#Controlled gates\|controlled Grover]] operations followed by inverse [[quantum Fourier transform]]; and according to the [[Quantum phase estimation algorithm#Analysis\|analysis]], we will find the best <math>p</math>-bit approximation to the [[real number]] <math>\theta</math> (belonging to the eigenvalues <math>e^{\pm i \theta}</math> of the Grover operator) with probability higher than <math>\frac{4}{\pi^2}</math>.<ref name = ekert>{{cite journal\|last1=Cleve\|first1=R.\|last2=Ekert\|first2=A.\|last3=Macchiavello\|first3=C.\|last4=Mosca\|first4=M.\|title=Quantum algorithms revisited\|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences\|date=8 January 1998\|volume=454\|issue=1969\|arxiv=quant-ph/9708016\|doi=10.1098/rspa.1998.0164\|bibcode=1998RSPSA.454..339C}}</ref>{{rp\|348}}<ref name = benet />{{rp\|157}}

	Note that the second register is actually in a [[quantum superposition\|superposition]] of the [[eigenvectors]] of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate <math>\theta</math>, and with some probability, we approximate <math>2\pi - \theta</math>; those two approximations are equivalent.<ref name = nielchuan />{{rp\|224–225}}		Note that the second register is actually in a [[quantum superposition\|superposition]] of the [[eigenvectors]] of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate <math>\theta</math>, and with some probability, we approximate <math>2\pi - \theta</math>; those two approximations are equivalent.<ref name = nielchuan />{{rp\|224–225}}

← Previous revision		Revision as of 15:35, 9 November 2022
Line 98:		Line 98:
	Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|last1=Imre\|first1=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}		Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of <math>M</math>, but we only wish to know whether <math> M \neq 0 </math> or not.<ref name=imres1>{{Cite book\|last1=Imre\|first1=Sandor\|last2=Balazs\|first2=Ferenc\|title=Quantum Computing and Communications - An Engineering Approach\|date=January 2005\|publisher=Wiley\|isbn=978-0470869024}}</ref>{{rp\|147}}

	A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead~~, i.e., to reduce its computational complexity from <math> \log^3(N) </math> to <math> \log^3(\sqrt{N}) </math>~~.<ref name = imres1 />{{rp\|148}}		A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields <math>M</math>, so by checking whether <math>M \neq 0</math> we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of <math>M</math>. Quantum phase estimation can be optimized to eliminate this overhead.<ref name = imres1 />{{rp\|148}}

	If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of <math>\theta</math>, but will suffice to determine whether <math>M</math> equals zero or not.<ref name = nielchuan />{{rp\|263}}		If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of <math>\theta</math>, but will suffice to determine whether <math>M</math> equals zero or not.<ref name = nielchuan />{{rp\|263}}