Quantum Computing Asked on July 25, 2021
Given we are using the computational basis,is there a quantum algorithm that can decide if an arbitrary input state $vert Arangle$ ( using $N$ qubits) is a pure state or a mixed state? $vert Arangle$ is defined below. If such an algorithm exists what is its space complexity and time complexity?
Where the arbitrary state $vert Arangle$ is the state
$$vert Arangle=a(0)|0rangle+a(1)|1rangle+a(2)|2rangle+ldots+ a(-1+(2^N))|(-1+(2^N))rangle$$
and, of course, the sum of squares of the amplitudes $a(0),a(1),a(2),…,a(-1+(2^N))$ is equal to $1$.
For the mixed or the pure state it is unknown which of the amplitudes are non zero; it is only known that $1$ non zero amplitude exists if $vert Arangle$ is a pure state; it is only known that more than $1$ non zero amplitude exists if $vert Arangle$ is a pure state. So if it is a pure state it means for some unknown $i$, $ a (i) =1$ and all the other amplitudes in the state $vert Arangle$ have amplitude zero. A mixed state is any other state which is not a pure state. Note that we only have one state $vert Arangle$ and we are not given any copies of this state $vert Arangle$.
After reading Narip’s comment I have added the update below.
Update:Another very closely related question is, does an algorithm exist using the standard definition of a pure state (with the computational basis) in above question? (i.e. instead of $ a (i) =1$ we have $ a (i) =c$ where c is a complex number with magnitude 1)
No, there is no quantum algorithm $mathcal{D}$ that given a single copy of a quantum state $rho$ as input determines whether $rho$ is pure or mixed.
By the principle of deferred measurement, we can assume that $mathcal{D}$ corresponds to a unitary $U$ followed by a measurement of an observable $M$. Suppose that the eigenvalue $lambda$ of $M$, with associated eigenspace projector $P_lambda$, is meant to signify that the input is pure. Further, assume that on pure input the last step in $mathcal{D}$, i.e. the measurement of $M$, yields $lambda$ with probability no less than $p$ (if $mathcal{D}$ is deterministic then $p=1$). Then
$$ mathrm{tr}(U|psiranglelangle psi|U^dagger P_lambda) ge p $$
for all pure states $|psirangle$. Now, consider a mixed state
$$ rho = sum_kp_k|kranglelangle k|. $$
By linearity, we see that
$$ mathrm{tr}(Urho U^dagger P_lambda) ge p. $$
Moreover, since the set of pure states is contained in the closure of the set of mixed states, by continuity we also get the converse. This means that $mathcal{D}$ fails to distinguish between pure and mixed states.
We will show that the ability to distinguish pure and mixed states confers the ability to solve all problems in NP. This means that, from computer science perspective, it is highly unlikely that a quantum algorithm for the task exists.
To that end, we will show how to use $mathcal{D}$ to solve SAT. Let $phi$ be a boolean formula with $n$ variables $x_1, dots, x_n$. There is a circuit $U_phi$ with size polynomial in the size of $phi$ such that
$$ U_phi|b_1dots b_nrangle|yrangle = |b_1dots b_nrangle|yoplus phi(b_1,dots,b_n)rangle $$
for $b_iin{0, 1}$ with $i=1,dots,n$.
In order to determine whether $phi$ is satisfiable, we proceed as follows. Prepare $n+1$ qubits in the $|0rangle$ state. Apply Hadamard to qubits $1$ through $n$. Apply $U_phi$ to all qubits.
At this point the $n+1$ qubits are in the pure state
$$ |psirangle = |psi_0rangle|0rangle + |psi_1rangle|1rangletag1 $$
where $|psi_0rangle$ is the unnormalized superposition of bitstrings corresponding to the unsatisfying assignments of $phi$ and $|psi_1rangle$ is the unnormalized superposition of bitstrings corresponding to the satisfying assignments of $phi$. If $phi$ has both satisfying and unsatisfying assignments then both terms in $(1)$ are non-zero and $|psirangle$ is entangled. Therefore, the state $rho=mathrm{tr}_{n+1}(|psiranglelanglepsi|)$ of qubits $1$ through $n$ is mixed. On the other hand, if $phi$ is constant, i.e. either all its assignments are satisfying or all its assignments are unsatisfying then one of the terms in $(1)$ is zero and $psi$ is separable. Consequently, $rho$ is pure.
Therefore, as the final step of our SAT solver we discard the qubit $n+1$ and feed qubits $1$ through $n$ to $mathcal{D}$. If $mathcal{D}$ indicates that the state $rho$ of qubits $1$ through $n$ is mixed then $phi$ is satisfiable. Otherwise, $phi$ is constant and we compute $phi(0, dots, 0)$ to check whether $x_1=dots=x_n=0$ is a satisfying assignment. If it is, then $phi$ is satisfiable. Otherwise, it is unsatisfiable.
Finally, SAT is NP-complete, so if $mathcal{D}$ exists then all problems in NP can be solved on a quantum computer.
The intuition behind the arguments above is that the set of pure states is a "razor thin" subset of the set of all states. More formally, it is a zero measure subset of the set of all states. The ability to determine membership in such a set is akin to a measurement of infinite precision and therefore unphysical.
Answered by Adam Zalcman on July 25, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP