theoretical computer science « While I think of the fundamental (im)possibilities and the larger picture

Practice problems on Mapping Reducibility

November 13, 2010 1 Comment

Let alphabet set be $\Sigma$ . Given two languages $A,B \subseteq \Sigma^*$ . $A$ is said to be mapping reducible to $B$ if there exists a Turing computable function $f$ s.t. $\forall x \in \Sigma^*,~ x \in A \Leftrightarrow f(x) \in B$ . When $A$ is mapping reducible to $B$ , we denote it as $A \leq_m B$ , $A \not \leq_m B$ otherwise.
In this post I mention a few practice problems on mapping reducibility, a subset of which were posed to the students of ics211 in 2009, Monsoon and cs3105 in 2010, Spring.

Consider the following languages :-

$L_1 = \{ < M,w > | M$ accepts w $\}$
$L_2 = \{ < M > | L(M) \neq \phi \}$
$L_3 = \{ < M_1,M_2 > | L(M_1) \cap L(M_2) \neq \phi \}$
$L_4 = \{ < M > | L(M) = \Sigma^{*} \}$
$L_5 = \{ < M > | L(M) = \{0^{n}1^{n}|n > 0\}\}$
$L_6 = \{ < M_1,M_2 > | L(M_1)=L(M_2)\}$
$L_7 = \{ < M_1,M_2 > | L(M_1)=\overline{L(M_2)}\}$

In the languages mentioned above $M,M_{1},M_{2}$ donote a Turing Machine.
Prove the following :-

$\forall i \in \{1,2,3\} ~ \forall j \in \{1,2,3,4,5,6,7\}, L_i \leq_m L_j$ .
$\forall i,j \in \{4,5,6,7\}, L_i \leq_m L_j$ .
$\forall i \in \{4,5,6,7\} ~ \forall j \in \{1,2,3\}, L_i \not \leq_m L_j$ .

Filed under puzzle, theoretical computer science

Quantum Teleportation

October 27, 2010 2 Comments

The process of making a physical object disappear at one place and making an exact replica of it appear at another place is known as Quantum Teleportation ( QT ). It was mere a science fiction until in 1993 when it was experimentally validated by C. H. Bennett , G. Brassard, C. Crépeau, R. Jozsa, A. Peres, W. K. Wootters. The Original paper is available here. In this post I present a QT algorithm without assuming any background in physics.
Let us first learn some basics of Quantum Mechanics necessary to understand the QT algorithm.
Any closed quantum mechanical system has an associated complex vector space ( CVS ). Such a CVS possesses a special property which we need not get into right now. At a given time instant, state of a system is described by a unit vector in the associated CVS. Evolution of a system is described by a unitary matrix $M$ ( one for which $MM^{\dagger} = I$ ).
Let vector $V$ denote the state of a quantum mechanical system and $M$ be any unitary matrix. When $M$ is operated on $V$ , system is in state $M \cdot V$ ( which is a unit vector again ).
Let’s consider a single qubit ( analogous of bit in quantum world ) system. Associated CVS is a complex plane $\mathbb{C}^2$ . In general, we denote the state of a single qubit system by $\alpha |0> + \beta |1>$ or $\left[ \begin{array}{ c } \alpha \\ \beta \\ \end{array} \right]$ interchangeably, where $|\alpha|^2+|\beta|^2 = 1$ .
Consider the following matrices :
$I =$ $\left[ \begin{array}{c c } 1 & 0 \\ 0 & 1 \\ \end{array} \right]$ , $X =$ $\left[ \begin{array}{c c } 0 & 1 \\ 1 & 0 \\ \end{array} \right]$ , $Y =$ $\left[ \begin{array}{c c } 1 & 0 \\ 0 & -1 \\ \end{array} \right]$ , $Z =$ $\left[ \begin{array}{c c } 0 & 1 \\ -1 & 0 \\ \end{array} \right]$ , $H =$ $\left[ \begin{array}{c c } \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \end{array} \right]$ .
One may verify that all the above mentioned matrices are unitary, and hence valid operators on all single qubit system.
We will be using these matrices pretty soon.
Let us now move on to 2-qubit systems. Associated CVS is $\mathbb{C}^4$ . In general, we denote state of a 2-qubit system by $\alpha_1 |00> + \alpha_2 |01> + \alpha_3 |10> + \alpha_3 |10> + \alpha_4 |11>$ or $\left[ \begin{array}{c} \alpha_1 \\ \alpha_2 \\ \alpha_3 \\ \alpha_4 \end{array} \right]$ interchangeably, where $\Sigma_{i=1}^{4} |\alpha_i|^{2} = 1$ . Consider the following matrix: $C =$ $\left[ \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right]$ . $C$ is a unitary matrix and hence a valid operator on any 2-qubit system. Let us operate $C$ on $\left[ \begin{array}{c c c c} \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \end{array} \right]^{T}$ :-
$\alpha_1 |00> + \alpha_2 |01> + \alpha_3 |10> + \alpha_4 |11>$ $\overset{C}\rightarrow$ $\alpha_1 |00> + \alpha_2 |01> + \alpha_4 |11> + \alpha_3 |10>$ .
Notice that, in $|i,j>$ , if $i=1$ , $j$ is flipped. Hence, operator $C$ is popularly known as controlled-not ( C-NOT) gate ( $i$ is called the control bit. If $i=1$ , $j$ is flipped).
Let us now consider a special state on a 2-qubit system, $| \psi> = \frac{1}{\sqrt{2}}|00>+\frac{1}{\sqrt{2}}|11>$ , popularly known as Bell state.
In a 2-qubits closed systems, it is possible to put the two qubits far apart maintaining the state of the system.
Ok. We are done with the preliminaries . Let us move on to give the problem statement.

Formal problem statement for Quantum Teleportation :-
Alice and Bob live far apart. They share a qubit each of a 2-qubit system in Bell state. Alice has a telephone facility with which she can send 2 bits of information to Bob. Alice has a 1-qubit system which she wishes to send to Bob. In this entire process, Alice doesn’t care if she is not left with a copy of qubit she intended to send to Bob.

Algorithm:-
Let $|\psi> = \alpha |0> + \beta |1>$ be the state Alice intends to send to Bob. Consider the system,
$|\psi> \otimes \frac{|00>+|11>}{\sqrt{2}}$ $\equiv$ $\alpha |0> + \beta |1> \otimes \frac{|00> + |11>}{\sqrt{2}} \equiv \alpha |0> \otimes \frac{|00>+ |11>}{\sqrt{2}} + \beta |1> \otimes \frac{|00>+|11>}{\sqrt{2}}$ .

Alice operates C-NOT on the two qubits in her possession :-
$\alpha |0>\otimes \frac{|00>+ |11>}{\sqrt{2}} + \beta |1> \otimes \frac{|00>+|11>}{\sqrt{2}}$ $\overset{C-NOT}\rightarrow$ $\alpha |0> \otimes \frac{|00>+ |11>}{\sqrt{2}} + \beta |1> \otimes \frac{|10>+|01>}{\sqrt{2}}$ .

Alice then operates $H$ on the first of the two qubits in her possession :-
$\alpha |0>\otimes \frac{|00>+ |11>}{\sqrt{2}} + \beta |1> \otimes \frac{|00>+|11>}{\sqrt{2}}$ $\overset{H} \rightarrow$ $\alpha \frac{|0> + |1>}{\sqrt{2}} \otimes \frac{|00>+ |11>}{\sqrt{2}} + \beta \frac{|0> - |1>}{\sqrt{2}} \otimes \frac{|10>+|01>}{\sqrt{2}}$ .

Re-arranging terms, we can equivalently represent the state of the system as :-
$\frac{|00>}{2} \otimes ( \alpha |0> + \beta |1> ) + \frac{|01>}{2} \otimes ( \alpha |1> + \beta |0> ) +$
$\frac{|10>}{2} \otimes ( \alpha |0> - \beta |1> ) + \frac{|11>}{2} \otimes ( \alpha |1> + \beta |0> )$ .

Alice now measures the qubits in her possession :-
Outcome of the measurement & the corresponding new state of the system respectively are as shown in the table below :-
$\begin{array}{c | c } 00 & \alpha |0> + \beta |1> \\ 01 & \alpha |1> + \beta |0> \\ 10 & \alpha |0> - \beta |1> \\ 11 & \alpha |1> - \beta |0> \end{array}$ .

Alice communicates the outcome of the measurements to Bob, which is 2 bit of information.
Notice that the qubit in Bob’s possession is in one of the four states mentioned in the table, depending on the outcome of the Alice’s measurement.

Bob on receiving 2 bits from Alice does the following operation on the single qubit in his possession.
1. If Bob receives 00, he does nothing.
2. If Bob receives 01, he operates $X$ .
3. If Bob receives 10, he operates $Y$ .
4. If Bob receives 11, he operates $Z$ .

Now, the qubit in Bob’s possession is in the state $|\psi> (= \alpha |0> + \beta |1>$ ).

Related homework problems,
1. Show that, when a unit vector is multiplied with a unitary matrix, the resulting vector is also a unit vector.
2. How to teleport a 2-qubit system? In general, how to teleport a n-qubit system ?
3. It is obvious that teleporting a n-qubit (n > 1) system cannot be done with just a pre-shared EPR pair between Alice and Bob. What is the minimum entanglement necessary to achieve the teleportation ?

Any progress w.r.t 2nd question, enlighten me too . I’ve been struggling with it since quite some time now.

Filed under theoretical computer science

Godel’s Second Incompleteness Theorem

July 29, 2010 2 Comments

A formal system is characterized by its axiom set. In this post, I talk about systems with only finitely many axioms. A system is said to be consistent if its axioms do not contradict any of its axioms. In a system, a statement is said to be independent of the system if it is not derivable from its axioms logically.

Godel’s Second Incompleteness Theorem states: If a system is consistent, then the consistency of the system is not provable within the system.
More formally one may state the theorem as: If a system $S$ is consistent, then the proof of the statement “ $S$ is consistent” is independent of $S$ .

It follows that, if there is a proof of consistency of a system within the system then it is necessarily inconsistent ( contra positive of the theorem statement ). The surprise element related to this theorem is, say some postulates such as Euclid’s postulates to do 2-d geometry are consistent, then this very fact forbids us from giving a proof of postulates being consistent. One may think of proving consistency of a system $S$ by moving to a higher system $S'$ , but then the consistency of $S$ relies on the consistency of $S'$ , and the problem of proving consistency of $S$ remains as such.

A related puzzle problem,
Consider a system $S$ with just one axiom, $A$ : 0 is a number.
Consistency proof:-
Since nothing is derivable with just one axiom, hence the only axiom $A$ does not contradict itself. Hence, $S$ is a consistent system.

$S$ is consistent and we have a consistency proof for $S$ . too.
Isn’t this a counter example to Second Incompleteness Theorem? Why not ?

Filed under puzzle, theoretical computer science

A Buggy Argument to #real numbers = #natural numbers

July 21, 2010 4 Comments

A real line is a line whose points correspond to real numbers.
1. Let $N_1$ be the number of points on a real line
2. Let $N_2$ be the number of points in [-1,1] interval over a real line.
3. Let $N_3$ be the number of points in (-1,1) interval over a real line.
4. Let $N_4$ be the number of points in a unit square.

$N_1$ seem to be infinitely greater than $N_2$ and $N_2$ seem to be some twoish greater than $N_3$ . $N_4$ seem to be quite a lot bigger than $N_3$ . Georg Cantor created a paradise, a theory of sets which suggests $N_1 = N_2 = N_3 = N_4$ . Now this is something hard to digest at the first sight, but that’s the way it is.

Later on, Russell proved that the Cantor’s theory of sets is inconsistent i.e. it’s axioms are self-contradictory. This doesn’t mean that the above mentioned equalities do not hold, one may use ZFC theory of sets ( which is immune to various paradoxes which Cantor’s theory faced ) to arrive at the same result. Though ZFC hasn’t witnessed a paradox yet and is widely believed to be consistent, we still do not know whether it is a consistent theory of sets or not since Godel‘s second incompleteness theorem states that the consistency of a formal system S can be proved within the system only if it is inconsistent ( or equivalently we can say that if a system is consistency then it’s consistency can not be proved within the system) and hence forbids us from proving the consistency of ZFC within ZFC.

Let $\mathbb{N}$ be the set of natural numbers and $M$ be the set of all the subsets $\mathbb{N}$ . Cantor proved that $|\mathbb{N}| < |M|$ . With this proof he also contributed a technique known as Diagonalization, very useful tool in theoretical computer science.
Other day I was playing with the sets, $\mathbb{N}, M$ and arrived at a mapping $f:\mathbb{N} \rightarrow M$ as described below. One may trivially show that $f^{-1}$ exists and hence $f$ is a bijection between $\mathbb{N}$ and $M$ ( i.e. $|\mathbb{N}| = |M|$ )!!

Description of $f$ :
i=1;n=1;
while(1) {

$A$ be the set of all those set $S \subseteq \mathbb{N}$ with $\displaystyle\sum_{s \in S}s=i$ ;
for each {
- map $Z$ to n;
- n++;
}
i++;

}

Few example mapping by the function $f$ :-
{1}->1,
{2}->2,
{1,2}->3, {3}->4,
{1,3}->5, {4}->6,
{2,3}->7, {1,4}->8, {5}->9,
{1,5}->10, {2,4}->11, {1,2,3}->12, {6}->13,
{1,6}->14, $\ldots$

Now given that Cantor gave a clean proof for $|\mathbb{N} < |M|$ , something has to be wrong with argument given above which claims $|\mathbb{N}| = |M|$ . What is it?
Note that I have detailed $f$ as an infinite loop mapping. One may instead detail $f$ as a function which takes a set $Z$ as input and outputs $f(Z)$ , a natural number.

PS: You can post your doubts/comments/solutions in the comments section or mail them to me.

Filed under puzzle, theoretical computer science

A Special Case of Hilbert’s Tenth Problem

July 19, 2010 6 Comments

In 1900, David Hilbert posed a list of 23 quality problems in mathematics, many of them remain unsolved till date. These problems have caused a significant progress in various disciplines of mathematics. Briefings and current status of the problems can be found here. In this post, I am going to brief Hilbert’s Tenth Problem and pose a related puzzle problem.

A root of a multivariate polynomial $p(x_1,x_2,\ldots,x_n)$ are values of variables $x_1,x_2,\ldots,x_n$ at which $p$ vanishes to 0. Hilbert in his 10th problem asked for an algorithm for the following decision problem: Given a multivariate polynomial with integral coefficients as input, if there are any integral roots to it. (For example, $p(x,y)=x^2y^2+x-2$ has integral roots and $p(x,y,z)=2x^2+2y^2+2z^2-1$ has no integral roots.)

In 1970, Yuri Matijasevic proved that there can not exist an algorithm for the problem. But what about the special case when the input polynomials are univariate only i.e. Does there exist an algorithm which when given a univariate polynomial with integral coefficients as input tells if at all there are any integral root to it? If yes, then what would be the best possible algorithm for this with respect to time complexity ( i.e. the number of steps it takes to arrive at the answer (yes/no) on the worst case input to your algorithm).

PS: People can post their (full/partial) solutions in the comments section.

Filed under puzzle, theoretical computer science

	amehta on A Buggy Argument to #real numb…
	Yuri on A Buggy Argument to #real numb…
	amehta on Quantum Teleportation
	djranga on Quantum Teleportation
	Hiran on Practice problems on Mapping…

While I think of the fundamental (im)possibilities and the larger picture

Practice problems on Mapping Reducibility

Quantum Teleportation

Godel’s Second Incompleteness Theorem

A Buggy Argument to #real numbers = #natural numbers

A Special Case of Hilbert’s Tenth Problem

Links

Recent Comments

Recent Posts

Blog Stats

Flickr Photos

Archives

Follow “While I think of the fundamental (im)possibilities and the larger picture”

May 2012
M	T	W	T	F	S	S
« Nov
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31