Quantum computational complexity - Revision history

RobinK: ←Redirected page to Quantum complexity theory

2009-09-28T00:14:15Z

←Redirected page to Quantum complexity theory

← Previous revision		Revision as of 00:14, 28 September 2009
Line 1:		Line 1:
			#REDIRECT [[Quantum complexity theory]]
	#REDIRECT [[Quantum_computer#Relation_to_computational_complexity_theory]]

RobinK: ←Redirected page to Quantum computer#Relation to computational complexity theory

2009-09-22T00:10:42Z

←Redirected page to Quantum computer#Relation to computational complexity theory

← Previous revision		Revision as of 00:10, 22 September 2009
Line 1:		Line 1:
			#REDIRECT [[Quantum_computer#Relation_to_computational_complexity_theory]]
	#REDIRECT [[computational complexity theory]]

Bryan Derksen: don't know if it's important or not, but turned redirected link into an actual link

2002-04-26T08:16:58Z

don't know if it's important or not, but turned redirected link into an actual link

← Previous revision		Revision as of 08:16, 26 April 2002
Line 1:		Line 1:
	#REDIRECT [computational complexity theory]		#REDIRECT [[computational complexity theory]]

163.1.103.122: redirecting to computational complexity; which includes quantum classes

2002-04-26T03:48:16Z

redirecting to computational complexity; which includes quantum classes

← Previous revision		Revision as of 03:48, 26 April 2002
Line 1:		Line 1:
	~~===~~ ~~Classical communication~~ complexity ~~===~~		#REDIRECT [computational complexity theory]

	The notion of communication complexity (CC) was introduced by Yao
	in 1979, who investigated the following problem involving two
	separated parties (Alice and Bob). Alice receives a n-bit string x
	and Bob another n-bit string y, and the goal is for one of them
	(say Bob) to compute a certain function f(x,y) with
	the least amount of communication between them. Note that here we are
	not concerned about the number of computational steps, or the size of
	the computer memory used. Communication complexity tries to quantify
	the amount of communication required for such distributed
	computations.

	Of course they can always succeed by having Alice send her whole
	n-bit string to Bob, who then computes the function, but the idea
	here is to find clever ways of calculating f with less than n$ bits
	of communication.

	This abstract problem is relevant in many contexts: in
	VLSI circuit design, for example, one wants to minimize energy
	use by decreasing the amount of electric signals required between the
	different components during a distributed computation. The problem is
	also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

	=== Quantum communication complexity ===

	Quantum communication complexity tries to quantify the
	communication reduction possible by using quantum effects during a
	distributed computation.

	At least three quantum generalizations of CC have been
	proposed; for a survey see the suggested text by G. Brassard.

	The first one is the
	qubit-communication model, where the parties can use quantum
	communication instead of classical communication, for example
	by exchanging photons through an optical fiber.

	In a second model the communication is still performed with
	classical bits, but the parties are allowed to manipulate an unlimited
	supply of quantum entangled states as part of their protocols. By doing
	measurements on their entangled states, the parties can save on classical
	communication during a distributed computation.

	The third model involves access to previously shared entanglement in
	addition to qubit communication, and is the least explored of the
	three quantum models.

	References:
	* Kushilevitz, E. and Nisan, N. Communication complexity. Cambridge University Press, 1997.
	* Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005

Bryan Derksen: why was this article entered, and then immediately deleted again? reverting, until more is learned.

2002-04-25T22:14:16Z

why was this article entered, and then immediately deleted again? reverting, until more is learned.

← Previous revision	Revision as of 22:14, 25 April 2002
Line 1:	Line 1:
		=== Classical communication complexity ===

		The notion of communication complexity (CC) was introduced by Yao
		in 1979, who investigated the following problem involving two
		separated parties (Alice and Bob). Alice receives a n-bit string x
		and Bob another n-bit string y, and the goal is for one of them
		(say Bob) to compute a certain function f(x,y) with
		the least amount of communication between them. Note that here we are
		not concerned about the number of computational steps, or the size of
		the computer memory used. Communication complexity tries to quantify
		the amount of communication required for such distributed
		computations.

		Of course they can always succeed by having Alice send her whole
		n-bit string to Bob, who then computes the function, but the idea
		here is to find clever ways of calculating f with less than n$ bits
		of communication.

		This abstract problem is relevant in many contexts: in
		VLSI circuit design, for example, one wants to minimize energy
		use by decreasing the amount of electric signals required between the
		different components during a distributed computation. The problem is
		also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

		=== Quantum communication complexity ===

		Quantum communication complexity tries to quantify the
		communication reduction possible by using quantum effects during a
		distributed computation.

		At least three quantum generalizations of CC have been
		proposed; for a survey see the suggested text by G. Brassard.

		The first one is the
		qubit-communication model, where the parties can use quantum
		communication instead of classical communication, for example
		by exchanging photons through an optical fiber.

		In a second model the communication is still performed with
		classical bits, but the parties are allowed to manipulate an unlimited
		supply of quantum entangled states as part of their protocols. By doing
		measurements on their entangled states, the parties can save on classical
		communication during a distributed computation.

		The third model involves access to previously shared entanglement in
		addition to qubit communication, and is the least explored of the
		three quantum models.

		References:
		* Kushilevitz, E. and Nisan, N. Communication complexity. Cambridge University Press, 1997.
		* Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005

163.1.103.122: *

2002-04-25T04:15:03Z

← Previous revision		Revision as of 04:15, 25 April 2002
Line 1:		Line 1:
	=== Classical communication complexity ===

	The notion of communication complexity (CC) was introduced by Yao
	in 1979, who investigated the following problem involving two
	separated parties (Alice and Bob). Alice receives a n-bit string x
	and Bob another n-bit string y, and the goal is for one of them
	(say Bob) to compute a certain function f(x,y) with
	the least amount of communication between them. Note that here we are
	not concerned about the number of computational steps, or the size of
	the computer memory used. Communication complexity tries to quantify
	the amount of communication required for such distributed
	computations.

	Of course they can always succeed by having Alice send her whole
	n-bit string to Bob, who then computes the function, but the idea
	here is to find clever ways of calculating f with less than n$ bits
	of communication.

	This abstract problem is relevant in many contexts: in
	VLSI circuit design, for example, one wants to minimize energy
	use by decreasing the amount of electric signals required between the
	different components during a distributed computation. The problem is
	also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

	=== Quantum communication complexity ===

	Quantum communication complexity tries to quantify the
	communication reduction possible by using quantum effects during a
	distributed computation.

	At least three quantum generalizations of CC have been
	proposed; for a survey see the suggested text by G. Brassard.

	The first one is the
	qubit-communication model, where the parties can use quantum
	communication instead of classical communication, for example
	by exchanging photons through an optical fiber.

	In a second model the communication is still performed with
	classical bits, but the parties are allowed to manipulate an unlimited
	supply of quantum entangled states as part of their protocols. By doing
	measurements on their entangled states, the parties can save on classical
	communication during a distributed computation.

	The third model involves access to previously shared entanglement in
	addition to qubit communication, and is the least explored of the
	three quantum models.

	References:
	* Kushilevitz, E. and Nisan, N. Communication complexity. Cambridge University Press, 1997.
	* Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005

163.1.103.122: I explain both classical and quantum c.c.

2002-04-25T04:09:38Z

I explain both classical and quantum c.c.

New page

=== Classical communication complexity ===

The notion of communication complexity (CC) was introduced by Yao
in 1979, who investigated the following problem involving two
separated parties (Alice and Bob). Alice receives a n-bit string x
and Bob another n-bit string y, and the goal is for one of them
(say Bob) to compute a certain function f(x,y) with
the least amount of communication between them. Note that here we are
not concerned about the number of computational steps, or the size of
the computer memory used. Communication complexity tries to quantify
the amount of communication required for such distributed
computations.

Of course they can always succeed by having Alice send her whole
n-bit string to Bob, who then computes the function, but the idea
here is to find clever ways of calculating f with less than n$ bits
of communication.

This abstract problem is relevant in many contexts: in
VLSI circuit design, for example, one wants to minimize energy
use by decreasing the amount of electric signals required between the
different components during a distributed computation. The problem is
also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

=== Quantum communication complexity ===

Quantum communication complexity tries to quantify the
communication reduction possible by using quantum effects during a
distributed computation.

At least three quantum generalizations of CC have been
proposed; for a survey see the suggested text by G. Brassard.

The first one is the
qubit-communication model, where the parties can use quantum
communication instead of classical communication, for example
by exchanging photons through an optical fiber.

In a second model the communication is still performed with
classical bits, but the parties are allowed to manipulate an unlimited
supply of quantum entangled states as part of their protocols. By doing
measurements on their entangled states, the parties can save on classical
communication during a distributed computation.

The third model involves access to previously shared entanglement in
addition to qubit communication, and is the least explored of the
three quantum models.

References:
* Kushilevitz, E. and Nisan, N. Communication complexity. Cambridge University Press, 1997.
* Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005