Questions tagged [nielsen-and-chuang]

For questions about exercises or passages from the popular quantum computing textbook *Quantum Computation and Quantum Information* by Michael Nielsen and Isaac Chuang.

Filter by
Sorted by
Tagged with
3 votes
1 answer
112 views

Show that $E_k=(I\otimes\langle e_k|)U(I\otimes|e_0\rangle)$ implies $U=\begin{bmatrix}[E_1]&\cdots\\ [E_2]&\cdots\\\vdots&\ddots\end{bmatrix}$

In Page 365, Operator-sum representation, Chapter 8, Quantum Computation and Quantum Information by Nielsen and Chuang, it is given that We have a principal system $Q$ and an environment $E$ and $U$ ...
  • 383
4 votes
2 answers
245 views

Necessity of decoding in fault-tolerant quantum computation

On page 476 of Nielsen/Chuang's book it is stated: The basic idea of fault-tolerant quantum computation is to compute directly on encoded quantum states in such a manner that decoding is never ...
  • 41
0 votes
1 answer
62 views

Question regarding the measurement of Pauli matrices on a Bell state

Michael A. Nielsen & Isaac L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition p.113, Box 2.7 states that "if a measurement of $\vec v\cdot\vec\sigma$ is ...
  • 157
1 vote
1 answer
81 views

How can I represent the completely mixed state as $\frac I2=\frac14(\rho+X\rho X+Y\rho Y+Z\rho Z)$?

Consider the completely mixed state $I/2$. The equation comes from Eq.(8.101) of Nielsen's book: $\frac{I}{2}=\frac{\rho+X\rho X+Y\rho Y+Z\rho Z}{4}$, How comes this equation?
  • 359
2 votes
1 answer
133 views

Heisenberg Uncertainty Principle (Nielsen and Chuang Box 2.4)

I'm trying to follow Nielsen and Chuang Book on Quantum Computation and Quantum Information. There is Box 2.4 on the Heisenberg Uncertainty Principle. I got stuck pretty fast. In that box they define: ...
  • 167
2 votes
1 answer
126 views

What does the centered dot notation mean in the expression $|+\rangle|+\rangle\otimes(\cdot)$?

In the expression $|+\rangle|+\rangle \otimes(\cdot)$, what does the centered dot represent? I have come across a definition of the centered dot previously, similar to the one given here, but I am ...
1 vote
1 answer
114 views

Show the linearity of $(\langle a_m|\otimes I_B\otimes I_C\otimes \langle d_q|) U(I_{A}\otimes I_B\otimes |0_{C}\rangle\otimes |0_{D}\rangle)$

Suppose a composite system $AB$ initially in an unknown quantum state $\rho$ is brought into contact with a composite system $CD$ initially in some standard state $|0\rangle$, and the two systems ...
  • 383
0 votes
1 answer
58 views

Bit flip error correction syndrome measurements

I'm coming across some confusion in chapter 10.1.1 of Nielsen and Chaung. In terms of the 'recovery' procedure, how can the result of the syndrome measurement be 0, 2 or 3? I am assuming that, for ...
1 vote
2 answers
42 views

How is the grouping of terms done in the calculations for the teleportation circuit?

I have a CS background and am studying quantum computing by myself. Struggling at the moment with the Dirac notation for the teleportation circuit. Here we go: The circuit starts with the EPR pair ...
  • 145
0 votes
2 answers
145 views

CNOT gate an elementary example of a single qubit quantum operation

A natural way to describe the dynamics of an open quantum system is to regard it as arising from an interaction between the system of interest and an environment, which together form a closed quantum ...
  • 383
0 votes
0 answers
42 views

Composition of rotations sign

I'm solving exercise 4.15 from Nielsen and Chuang: Prove that if a rotation through an angle $\beta_1 $ about the axis $\hat{n}_1$ is followed by a rotation through an angle $\beta_2$ about an axis $\...
  • 1
0 votes
1 answer
77 views

What is the solution to Nielsen and Chuang Exercise 2.65?

Nielsen&Chuang Exercise2.65: Express the states (|0 + |1)/ √ 2 and (|0−|1)/ √ 2 in a basis in which they are not the same up to a relative phase shift. Consider an orthnormal basis :$\begin{cases}...
1 vote
1 answer
176 views

Hamiltonian Simulation Circuit for Grover's Search

The Hamiltonian in the simulation of Grover Search is given as, $H=|x\rangle\langle x|+|\psi\rangle\langle\psi|$. It is said that in order to simulate $H$ we can simulate the Hamiltonians $H_1=|x\...
  • 383
0 votes
0 answers
42 views

Usefulness of Heisenberg Uncertainty Principle

$ \newcommand{\ket}[1]{\left|#1\right\rangle} \newcommand{\bra}[1]{\left\langle#1\right|} $The Heisenberg Uncertainty principle as formulated in Nielsen and Chuang is $$ \Delta (C) \Delta (D) \geq \...
0 votes
1 answer
61 views

Question about proof that non-orthogonal states can't be reliably distinguished in QCQI

$$ \newcommand{\ket}[1]{\left|#1\right\rangle} \newcommand{\bra}[1]{\left\langle#1\right|} $$ The beginning portion of Box 2.3 on page 87 of QCQI is as follows: "Suppose such a measurement is ...
0 votes
1 answer
67 views

How can orthonormal vectors satisfy $\langle i|j\rangle=\delta_{ij}$?

In the book "Quantum Computation and Quantum Information" ("Mike and Ike") - chapter 2, page 66 - I have encountered the following paragraph: If the vectors i and j are ...
  • 1,237
0 votes
0 answers
32 views

Accuracy of Classical Counting problem

Consider a classical algorithm for the counting problem which samples uniformly and independently $k$ times from the search space, and let $X_1, ... ,X_k$ be the results of the oracle calls, that is, $...
  • 383
-1 votes
1 answer
210 views

Solution to problem 5.3 Book Quantum Computation and Quantum Information Nielsen Chuang regarding Kitaev's algorithm

Problem 5.3: (Kitaev’s algorithm) Consider the quantum circuit where |u> is an eigenstate of U with eigenvalue $e ^ {2 \pi i \phi} $. Show that the top qubit is measured to be 0 with probability $...
1 vote
1 answer
72 views

DFT like operation in the third step of Period finding and Discrete Logarithm algorithm

In the third step of the algorithm for discrete logarithm, the state $$ |\hat{f}(l_1,l_2)\rangle=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi il_2j/r}|{f}(0,j)\rangle $$ is introduced which is stated to ...
  • 383
2 votes
1 answer
60 views

Probability of success proof for Shor's algorithm

In the book "Quantum Computation and Information" by Nielsen and Chuang, Shor's algorithm is presented with a related probability of success theorem and proof found on page 634, Theorem A4....
2 votes
2 answers
57 views

In the order finding circuit, why is the equal superposition of the controlled unitary eigenstates the $|1\rangle$ state?

In Nielsen and Chuang's "Quantum Computation and Quantum Information" when the quantum order finding process is being presented (specifically page 227, equation 5.44) we are told that by &...
0 votes
0 answers
46 views

Mathematical reasoning of Repeating the Phase Estimation in the Order Finding Algorithm

Repeating the order-finding algorithm of quantum computing twice obtains $\dfrac{s_1'}{r_1'}$ the first time, and $\dfrac{s_2'}{r_2'}$ the second time, where $\dfrac{s_i'}{r_i'}$ is $\dfrac{s_i}{r}$ ...
  • 383
1 vote
0 answers
44 views

Probability of the case when $r'\neq r$ and $r'$ is a factor $r$ in the order finding algorithm

In the Order-Finding algorithm it is stated that it might be that $s$ and $r$ have a common factor, in which case the number $r'$ returned by the continued fractions algorithm be a factor of $r$, and ...
  • 383
2 votes
1 answer
76 views

Why do we need to reverse the order of qubits in Quantum Fourier Transform? [duplicate]

Looking at Qiskit's QFT tutorial, their implementation of QFT requires you to swap the qubits at the end (Nielsen and Chuang do this too). I'm wondering why this is the case. Can we flip the gates ...
2 votes
1 answer
58 views

Are the eigenvalues of projectors always zero and/or one?

Nielsen and Chuang, page 87, defining projective measurements, refers to projectors with "eigenvalue m." However, exercise 2.16 on page 70 seems to imply that the eigenvalue is always one or ...
4 votes
2 answers
207 views

The construction of every element of the Clifford group using H,S and CNOT circuits

I am trying to understand the following theorem: Every element $U\in C_n$ of the Clifford group can be constructed using $H, S, CNOT$ gates. In Nielsen and Chuang's book this is left as an exercise (...
  • 365
4 votes
1 answer
135 views

Cost of Modular Exponentiation in Shor's algorithm

In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as $$ U|y\rangle=|xy\;(\mod N)\rangle\text{ ...
  • 383
4 votes
1 answer
85 views

Understanding the 3rd step of Nielsen and Chuang's description of the quantum order-finding algorithm

In Nielsen and Chuang's description of Quantum order-finding algorithm, the 3rd step of the procedure says $$\frac1{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|x^j\mod N\rangle \approx \frac1{\sqrt{r2^t}}\...
1 vote
0 answers
41 views

Is there a way to use stabilizer formalism for non-computational basis input states?

In Nielsen and Chuang, exercise 10.42 is to use stabilizers to prove the teleportation circuit works as claimed. It has a footnote that it only works given a restricted class of inputs (it doesn't ...
  • 131
2 votes
1 answer
106 views

Is there a way to prove that the number of gates in Exercise 4.22 of Nielsen and Chuang's book is the smallest possible number?

I've been going over Nielsen and Chuang's Quantum Computation and Quantum Information and I ran into Exercise 4.22, which says, Prove that a $C^{2}(U)$ gate (for any single qubit unitary $U$) can be ...
3 votes
1 answer
123 views

What is the technique for calculating $\text{Tr}_b[{U(\rho\otimes\rho_b)U^{\dagger}}]$?

I am stuck on calculating $\mathcal{E}(\rho)=\text{Tr}_b[{U(\rho\otimes\rho_b)U^{\dagger}}]$. For example, in the case when $U$ is the CNOT matrix $$U=\begin{pmatrix} 1 & 0 & 0 & 0\\\ 0 &...
  • 177
4 votes
0 answers
86 views

Implementing "computable phase shifts" using T Toffoli ( problem 4.1 from Nielsen and Chuang's)

I am reading/studying the famous Nielsen and Chuang's book and ran into this interesting question and I don't quite understand the $f(x)$. It says it simply maps from $m$ to $n$ bits. But don't we ...
1 vote
1 answer
69 views

Grover search in Quantum Computation and Quantum Information (Nielsen and Chuang)

in Nielsen and Chuang's book in Box 6.1 (page 256 for 10th edition) there is a example of Grover's search algorithm for 3 qubits (2 as search space + 1 for oracle). I am currently trying to implement ...
  • 35
1 vote
1 answer
52 views

For bipartite mixed state, if one part is pure, then the global mixed state is a product state?

In Nielsen and Chuang, the chapter about Schmidt decomposition, there is an interesting result states that for a bipartite pure state $|\psi\rangle_{AB}$, if part A is a pure state, then $|\psi\...
  • 589
3 votes
0 answers
30 views

Proof of upper and lower bound (Gilbert-Varshamov bound) for linear code

I am trying to prove the following bounds for a $[n, k]$ code that can correct $t$ errors \begin{align} 1-H\left(\frac{t}{n}\right)\geq \frac{k}{n}\geq 1-H\left(\frac{2t}{n}\right) \end{align} where \...
  • 830
3 votes
2 answers
61 views

Are the states in the convex decomposition of a density matrix necessarily orthogonal?

In Nielsen and Chuang's QC&QI, I do not see a statement one way or another. In Steeb and Hardy's Problems and Solutions, orthogonality is asserted. If the $p_i$ in $\sum_i p_i |\psi_i\rangle\...
2 votes
2 answers
201 views

How to compute the unitary from the $\chi$ matrix obtained from QPT

I am trying to do quantum process tomography for one qubit and obtain the unitary for the gates that are applied on the qubit. I have studied the theory on process tomography from mike and ike and the ...
1 vote
0 answers
109 views

Definition(s) of $\delta$ in quantum phase estimation

I read the chapter on QPE (quantum phase estimation) in Nielsen and noticed that $\delta$ is defined there as follows: $0 \leq \delta \leq 2^{-t}$, see: 5.2.1 Performance and requirements The above ...
  • 638
1 vote
1 answer
71 views

Factoring Decision Problem - why not in P? [closed]

Nielsen and Chuang, 10th Anniversary Edition, page 142, refers to the following (classical) computation problem: Given a composite integer m and L <m, does m have a non-trivial factor less than L? ...
6 votes
1 answer
157 views

Register size in factoring 15 using Shor's algorithm

In Nielsen and Chuang's book: Quantum computation and quantum information (2016), there is an example in Box 5.4 which shows how to factor $15$ using Shor's algorithm. I am confused about a ...
  • 61
5 votes
1 answer
155 views

Derivation of efficiency of Phase Estimation Algorithm

In the section Performance and requirements of the phase estimation algorithm of Page 224, Quantum Computation and Quantum Information by Nielsen and Chuang In order to obtain Eq. 5.27 we have ...
  • 383
0 votes
1 answer
125 views

Equating the state of the Phase Estimation algorithm to $\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1} e^{2\pi i\phi k}|k\rangle$

It is stated in the Phase Estimation algorithm in Page 222, Quantum Computation and Quantum Information by Nielsen and Chuang that It seems to say that taking the inverse Quantum Fourier transform of ...
  • 383
3 votes
1 answer
86 views

When discussing error correction, what are the objects in the expression $PE_i^\dagger E_j P=\alpha_{ij} P$?

I've started reading the book "Quantum Computation and Quantum Information" by Michael A. Nielsen and Issac L. Chuang, specifically chapter 10 (about quantum error correction), and I'm ...
  • 51
1 vote
1 answer
66 views

Making sense of the terms Polynomial and Exponential Precision in a Quantum Circuit

The quantum circuit construction of the quantum Fourier transform apparently requires gates of exponential precision in the number of qubits used. However, such precision is never required in any ...
  • 383
1 vote
1 answer
53 views

What is meant by a "projection operator" in the book "Quantum Computation and Quantum Information"?

I've started reading the book "Quantum Computation and Quantum Information" by Michael A. Nielsen and Issac L. Chuang, specifically chapter 10 (about quantum error correction), and I'm ...
  • 51
1 vote
1 answer
58 views

What is the physical process causing a Bell state to be shared? [duplicate]

Nielsen and Chuang, QCQI, page 57, last paragraph, says "suppose Alice and Bob share between them a Bell state." I know how to prepare a Bell state, but what would be the physical process ...
2 votes
1 answer
49 views

Can every unitary on $\mathcal{H}\otimes \mathcal{K}$ be modelled by quantum operations on $\mathcal{H}$?

In section 8.2.3 of Nielsen and Chuang, they discuss how unitary dynamics of a system and environment arise from quantum operations (i.e. Kraus operators $E_k$ such that $\sum_k E_k^*E_k=I$). ...
  • 1,617
5 votes
1 answer
312 views

No-cloning theorem and distinguishing between two non-orthogonal quantum states revisited

There are a couple of posts on this question, but I think they are not satisfactory. The question is Nielsen and Chuang's QCQI, Exercise 1.2, page 57, which asks "Explain how a device which, upon ...
0 votes
1 answer
113 views

Phase estimation algorithm: Bounding of probability in Nielsen and Chuang

I am currently studying the Quantum Phase Estimation (QPE) algorithm as described in Nielsen and Chuang, pages 223-224. We have the following situation there, we have the state: $$\frac{1}{2^t} \sum\...
  • 638
0 votes
0 answers
29 views

prove that $E(U^m_{\Delta t},e^{-2miH\Delta t})\leq m\alpha \Delta t^3$ where $U_{\Delta t}=e^{-2iH\Delta t}+O(\Delta t^3)$

Let $H=\sum_{k=1}^LH_k$ and define $U_{\Delta t}=[e^{-iH_1\Delta t}e^{-iH_2\Delta t}\cdots e^{-iH_L\Delta t}][e^{-iH_L\Delta t}e^{-iH_{L-1}\Delta t}\cdots e^{-iH_1\Delta t}]=e^{-2iH\Delta t}+O(\Delta ...
  • 383

1
2 3 4 5 6