Questions tagged [quantum-information]

Theoretical issues related to the quantum treatment of information

Filter by
Sorted by
Tagged with
23
votes
5answers
7k views

Is there any connection between the diamond norm and the distance of the associated states?

In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
21
votes
7answers
28k views

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...
21
votes
1answer
7k views

Oracle Construction for Grover's Algorithm

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
19
votes
2answers
604 views

Quantum algorithms based on transforms other than Fourier transforms

In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier ...
19
votes
1answer
668 views

Does cryptography have an inherent thermodynamic cost?

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT ...
17
votes
1answer
1k views

Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of ...
16
votes
1answer
441 views

Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory. Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any ...
14
votes
5answers
1k views

The utility of Renyi entropies?

Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic ...
14
votes
2answers
1k views

Best method of Error Correction in Quantum Key Distribution

As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared ...
14
votes
2answers
789 views

Complexity of optimization over unitary group

What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...
13
votes
1answer
1k views

Entropy and computational complexity

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
12
votes
4answers
1k views

Master Equations and Operator Sum Form

I'm more of a quantum optics guy than a quantum info guy, and deal mainly in master equations. I'm interested in operator-sum form, and I'd like to derive the errors in this form for a small quantum ...
11
votes
2answers
2k views

Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

I believe the answer to this question is well-known; but, unfortunately, I don't know. In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the ...
11
votes
7answers
1k views

Quantum Computation - Postulates of QM

I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book. I wanted to ask if anyone could try finding time to help me with whats going on with the ...
11
votes
2answers
561 views

Nonlocal Games and Quantum Communication

I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at ...
11
votes
1answer
243 views

Generating "infinite" randomness from a constant number of sources

I recently came across a paper by Coudron and Yuen on randomness expansion using quantum devices. The main result of the work is that it is possible to generate "infinite" randomness from a constant ...
11
votes
1answer
498 views

Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$? This problem can be ...
11
votes
1answer
277 views

Fast classical simulation of quantum algorithms

Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have ...
11
votes
1answer
293 views

Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others). ...
10
votes
4answers
487 views

Quantum Bell-Type Inequalities

I'm curious if someone could recommend some supplementary material for gaining a deeper understanding of the paper : "Some Results and Problems on Quantum Bell-Type Inequalities - Tsirelson". ...
10
votes
1answer
88 views

Optimal measurement for MUBs

Let $\mathcal{B} = \{B_1, \dots, B_k\}$ be a set of Mutually Unbiased Bases (MUB) in $\mathbb{C}^n$, i.e. each $B_i$ is an orthonormal basis and for $v \in B_i, w \in B_j, i \neq j $ we have $|\langle ...
10
votes
0answers
250 views

How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?

A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied ...
10
votes
0answers
152 views

Threshold for non-zero quantum capacity of depolarizing channels

In "Quantum-channel capacity of very noisy channels", DiVincenzo, Shor and Smolin showed that it is possible to perform quantum communication over depolarizing channels provided that the fidelity was ...
9
votes
2answers
840 views

Is adiabatic quantum computing as powerful as the circuit model?

Much of the quantum computing literature focuses on the circuit model. Adiabatic quantum computing is not based on applying a sequence of unitary operators, but on changing a time-dependent ...
9
votes
2answers
261 views

Polynomial algorithms for UPB (Unextendable Product Bases)

Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n ...
9
votes
0answers
112 views

Non-tomographical certification of projectors, using product states?

I'm interested in operational ways of demonstrating (with high probability of confidence, in an error-free setting) that a POVM operator on n-qubit states is a projector. Specifically, I'm interested ...
8
votes
4answers
2k views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
8
votes
1answer
200 views

Where can I find examples of error correcting codes of the following types?

First, apologies if this question is in appropriate or trivial for this site. I'm a physicist looking for some help outside his comfort zone. In PRL 87 167902 (2001) it is claimed that "...for an ...
8
votes
1answer
5k views

Quantum annealing vs adiabatic quantum computation

I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
8
votes
2answers
203 views

Largest set allowing one-step unstructured quantum search

What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle? The question is interesting since Grover'...
8
votes
0answers
341 views

Approximation of Quantum Channels

Background: In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels: A quantum channel is a linear, ...
7
votes
1answer
207 views

A promise problem to decide whether two given pure quantum states are close or far apart

Consider this problem in quantum cryptography: We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which $$\left|\...
7
votes
1answer
434 views

Quantum Money where not even the Bank can counterfeit

The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties: The bank can produce bank notes in the form of quantum states. Anyone can verify that ...
7
votes
1answer
1k views

The computational complexity of spectral norm of a matrix

How hard is computing the spectral norm of a matrix? This paper says, ... it suffices to say that, except for few particular cases, the Matrix Norm problem is NP-hard. I expected that the ...
7
votes
1answer
909 views

States and Probability distributions that the 5-qubits IBM computer can produce

Update (January 2018) A new very interesting paper with various experiments on the IBM machine is Five Experimental Tests on the 5-Qubit IBM Quantum Computer by Diego García-Martín, Germán Sierra. ...
7
votes
0answers
64 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
7
votes
0answers
269 views

Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme

I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled '...
6
votes
1answer
818 views

Analytic solutions in semidefinite programming (SDP)

From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
6
votes
1answer
295 views

Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel

I am aware that quantum entanglement cannot increase the asymptotic capacity of a noiseless classical channel. However, can anyone provide some type of reference in the literature that contains a ...
6
votes
1answer
1k views

Applications of HHL's algorithm for solving linear equations

In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge ...
6
votes
1answer
384 views

Quantum capacity for ensemble of Pauli channels

In Preskill's quantum computing notes Chapter 7 approximate page 82, he shows that a Pauli channel has capacity $Q \geq 1-H(p_I,p_X,p_Y,p_Z)$ where $H$ is Shannon entropy and $p_I, p_X, p_Y, p_Z$ are ...
6
votes
0answers
150 views

"Looking for help understanding a proof by Gossner (1998)."

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
6
votes
0answers
175 views

Local Hamiltonian and combinatorial search problems

I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination ...
5
votes
1answer
254 views

Quantum Channel Decoding

Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$. What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ? $\forall $...
5
votes
1answer
175 views

Communicating a string of zeros and ones quantumly

Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and transmits a ...
5
votes
2answers
565 views

Are two-qubit unitaries necessary for universal quantum computation?

I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said, Two-qubit ...
5
votes
1answer
136 views

Known properties of a specific class of quantum states

Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as $|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n (-1)^{x_i}|i\rangle$,...
5
votes
1answer
171 views

Shor's quantum error correction code with unknown basis

$\newcommand{\ket}[1]{\lvert #1 \rangle}$I've met a problem in quantum secret sharing which involves the use of a quantum error-correction code. (let's make it simple to be the 9-qubit Shor code) In ...
5
votes
0answers
124 views

Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
4
votes
1answer
394 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a positive ...