6 votes
Accepted

Can a quantum computer run classical algorithms?

Quantum computers can run classical computations using exactly the same algorithms, and hence have the same running time in terms of scaling. For example, if you look at shor’s algorithm, a major ...
DaftWullie's user avatar
  • 55.7k
6 votes
Accepted

Trace distance of two classical-quantum states

Yes, since the trace norm is the sum of the absolute value of the singular values, and the singular values can be found for each of the $a$ blocks independently.
Norbert Schuch's user avatar
5 votes

Can error correction for a classical algorithm with bit flips be easier than for a general quantum circuit?

Can implementing error correction in this case be any easier than in the case of a general quantum circuit? Yes, for example you could use a classical error correcting code such as a repetition code. ...
Craig Gidney's user avatar
  • 33.3k
5 votes

Is the set of classical-quantum states convex?

Your mistake is that you assume that $\rho$ and $\sigma$ are classical-quantum in the same classical basis on $X$. However, there is no need to do so -- all which is necessary is that there exists ...
Norbert Schuch's user avatar
5 votes
Accepted

Does the quantum Jensen-Shannon divergence appear in any quantum algorithms or texts on quantum computing?

That quantity appears to be identical to Holevo information, which turns out to be the upper bound on how much classical information you can transmit using a quantum channel [1]. More generally the ...
forky40's user avatar
  • 6,143
5 votes

Example of a quantum algorithm better than its classical counterpart which involves only $1$ qubit?

There aren't many examples! The main reason for advantages in quantum computers is the ability to constructively combine amplitudes - if you've only got 1 qubit, there aren't any amplitudes to combine!...
C. Kang's user avatar
  • 1,684
4 votes
Accepted

What does superposition do for quantum probabilistic sampling?

Classical computers are inherently deterministic, so they either generate pseudorandom numbers, or use an external physical process with statistically random noise to generate random numbers. Quantum ...
Jonathan Trousdale's user avatar
4 votes
Accepted

Bounding diamond norm distance using probability of error in transmission of classical information

Intuition The expression $\|\mathcal{A} - \mathcal{I}\|_\diamond$ quantifies how close the channel $\mathcal{A}$ is to the identity channel $\mathcal{I}$ which is the channel that preserves quantum ...
Adam Zalcman's user avatar
  • 20.8k
3 votes
Accepted

Understanding the association rule between classical to quantum data $|x\rangle=\frac{1}{|\vec x|_2}\sum_{i=1}^d x_i|i\rangle$

It may be easier to understand how this works in terms of the computational basis if you choose $d$ to be some power of $2$. So let $d=2^n$ and then we will use $n = \log_2 d$ qubits to represent the ...
forky40's user avatar
  • 6,143
3 votes

Can error correction for a classical algorithm with bit flips be easier than for a general quantum circuit?

Peter Shor has two error correcting methods. One is the bit flip method and the other is the phase shift method. The bit flip method is similar to what you could use in classical computing, and is ...
user440774's user avatar
3 votes
Accepted

Prove that for a pure tripartite state $\rho_{ABE}$, $H(RB) = H(RE)$

As $\rho_{ABE}$ is pure we have $\rho_{ABE} = |\psi\rangle \langle \psi|$. We'll rewrite the output of the channel $\mathcal{R}$ as $$ \rho_{ABE}' = \sum_j (P_j \otimes I_{BE}) |\psi\rangle \langle \...
Rammus's user avatar
  • 5,355
3 votes
Accepted

Prove that the conditional entropy of a classical-quantum state is non-negative

We will use the upper bound on the entropy of a mixture (for proof see for example theorem 11.10 on p.518 in Nielsen & Chuang) $$ S\left(\sum_k p_k \rho_k\right) \leq H(p) + \sum_k p_k S(\rho_k)\...
Adam Zalcman's user avatar
  • 20.8k
3 votes
Accepted

Relating quantum max-relative entropy to classical maximum entropy

As far as I'm aware there isn't much of a meaningful connection. The corresponding entropy for $D_{\max}$ is the min-entropy (written $H_{\min}$ or $H_{\infty}$). It measures a sort of `worst case' ...
Rammus's user avatar
  • 5,355
3 votes
Accepted

Translating classical math and code to quantum math and code

Bra-ket notation is not necessarily tied to "quantum math," it's simply a convenient notation in many circumstances. It may seem intimidating at first, but once you understand the basics (ket = ...
Jonathan Trousdale's user avatar
3 votes

Translating classical math and code to quantum math and code

At least currently, most of the translations being made are in extraordinarily specialized areas - for example, quantum chemistry / computational chemistry. A lot of the math involves mapping domain ...
C. Kang's user avatar
  • 1,684
2 votes

How to initialize classical register in Qiskit?

Classical registers are typically used for capturing measurement results, and may also be used for conditionally applying quantum operation. See: https://github.com/Qiskit/openqasm/blob/master/spec/...
James Weaver's user avatar
2 votes

Classical and quantum limits to classical copying?

You seem to be mixing two very different concepts here. Quantum cloning is talking about the absolute limits of what is theoretically possible in a perfect world. In this absolute theoretical limit, ...
DaftWullie's user avatar
  • 55.7k
2 votes

Better Way Of Separating Two CQ-States

In quantum information theory, the standard way to obtain what it is called reduced density operator from a quantum system composed by several quantum states is to use the so-called partial trace ...
Josu Etxezarreta Martinez's user avatar
2 votes

Is "classical information" the same as "Shannon information"?

I don't think there is a canonical "right" answer to this question as there is no universal formulation of the terminology, so let me try and pick apart a few of the things you mention, and ...
DaftWullie's user avatar
  • 55.7k
2 votes
Accepted

Trace distance of two classical-quantum state with hashing

No, this is not possible. The existence of such a hash function requires the (smooth) min-entropy of the initial state to be large enough but does not depend on its trace distance from a uniform state....
Rammus's user avatar
  • 5,355
2 votes
Accepted

How to copy value from classical register to quantum register?

I would suggest working with Qiskit rather than IBM Quantum Composer in that case, because Qiskit supports the feature you are asking for, and IBM Quantum Composer supports it only partially. The ...
Ohad's user avatar
  • 1,709
2 votes

Is there any real world problem where I can see quantum computing being better than classical computing?

You probably did not look good enough. Every fundamental quantum algorithm is always presented and compared to a classical counterpart. There is simply no well-known quantum algorithm that was ever ...
MonteNero's user avatar
  • 2,369
2 votes
Accepted

Showing that $S(\rho_{XB}||\sigma_{XB})=\sum_{x}p(x)D(\rho_{B}^{x}||\sigma_{B}^{x})$ for classical-quantum states

As you say, $$ \mathrm{Tr}[\rho_{XB} \log \rho_{XB}] = -S(X) + \sum_{x} p(x) \mathrm{Tr}[\rho_{B}^x \log \rho_B^x]. $$ But if you can prove the above statement, then the exact same derivation gives ...
Rammus's user avatar
  • 5,355
2 votes

What is the difference between classical-quantum and completely classical states?

Your expressions give a pretty clear distinction: in the classical-quantum state, the eigenbases $\left|y_x\right>$ can be different for different states $x$ of the classical register $A$, and in ...
Vladimir Lysikov's user avatar
1 vote
Accepted

Is Classical-Classical-Quantum state equivalent to Classical-Quantum state?

Say you have a pair of sets $\mathcal{X} = \{x(1), x(2), \dots, x(|\mathcal{X}|)\}$ and $\mathcal{Y} = \{y(1), y(2), \dots, y(|\mathcal{Y}|)\}$. Then we can define random variables $X, Y$ taking ...
forky40's user avatar
  • 6,143
1 vote
Accepted

How should $\rho(b,b')$ be interpreted in the context of classical-quantum state

First of all, the authors define on page 6 that: A density matrix that is diagonal in the computational basis corresponds to a classical random variable. and A classical-quantum state is a state of ...
Tristan Nemoz's user avatar
1 vote

How should $\rho(b,b')$ be interpreted in the context of classical-quantum state

$\rho$ is a probability distribution. $\rho(X)$ is a probability distribution with support of a single random variable, $X$. $\rho(X,Y)$ then is a probability distribution with support of two random ...
Simon Yin's user avatar
  • 334
1 vote

What is the general form of a classical-quantum state?

Your description has X as a mixed state (a quantum state with classical uncertainty) and not a classical state. For example you can apply quantum gates to X but that shouldn’t be allowed if X was a ...
shashvat's user avatar
  • 705
1 vote

Counting Achievable Operations

Why is 4! valid? We can imagine the desired operation to implement as a truth table / permutation matrix. Recognize that we may do this because none of the operations actually modify the amplitudes - ...
C. Kang's user avatar
  • 1,684
1 vote

The effect of available information on random quantum channels

This question gets right to the heart of what information does a density matrix contain about the state of a qubit. Critically, it is a subjective state of knowledge. So, if I don't know the outcome ...
DaftWullie's user avatar
  • 55.7k

Only top scored, non community-wiki answers of a minimum length are eligible