Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [quantum-information]

Theoretical issues related to the quantum treatment of information

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

Can a collection of quantum circuits be calculated in superposition state?

My question is that, assuming there exist a sampler $\mathtt{S}$ (probably classically efficient) takes $x\in\{0,1\}^{n}$ as input and outputs a quantum polynomial-time circuit $\mathtt{S}(x)= Q_{x}$ ...
0 votes
0 answers
57 views

Does Co-occurrence Information Differ Qualitatively From Shannon and Algorithmic Information?

In Distributed Computation as Hierarchy Michael Manthey argues that co-occurrence of indistinguishables (critical for quantum theory) supplies spatial information that qualitatively differs from both ...
1 vote
1 answer
61 views

Impact HHL caveat relaxation on quantum advantage

We know that there are four caveats for the exponential speedup proven for the HHL algorithm. Could anyone answer how that exponential speedup evolves as we relax the caveats? For example, the ...
22 votes
3 answers
9k 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 ...
0 votes
2 answers
402 views

Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory

Anyone has proved the error rate of quantum computation is bounded by (less than) a constant rather than a function dependent on time and environment by quantum theory? For error rate and error ...
0 votes
1 answer
86 views

Vidick's proof of parallel DI-QKD

This question is based on the paper- https://arxiv.org/abs/1703.08508. As far as I understand, for this proof Vidick uses a quantum parallel repetition for 3 player- Alice, Bob and Eve but the results ...
3 votes
1 answer
1k views

From CHSH inequality to CHSH game

I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
1 vote
0 answers
46 views

Quantum Communication Complexity Bound on Vector Inner Product

Say Alice has a (complex) vector $a\in\mathbb{C}^d$, and interacts with Bob in a quantum communication protocol (sending qubits back and forth). At the end of the protocol, Bob produces a guess $b\in\...
8 votes
3 answers
582 views

What are some "must-read" papers for someone getting into Quantum Cryptography?

I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would ...
3 votes
0 answers
101 views

Worst to average case reductions for quantum complexity classes

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
9 votes
0 answers
160 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 ...
2 votes
2 answers
2k views

Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
1 vote
0 answers
37 views

Am I manipulating the content of states when I manipulate a superposition of indices?

I posted this question on quantumcomputing forum but I think maybe is more adequate to cstheory. I'm trying to understand something, I have been reading some papers about Grover's iterator, especially ...
12 votes
4 answers
3k 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 ...
3 votes
1 answer
438 views

Noisy channel coding theorem in quantum information

Why Shannon's noisy channel coding theorem can't be used for quantum communication applications? Schumacher proved the first Noiseless theorem and there are quantum error correction mechanisms out ...
4 votes
1 answer
240 views

Survey on Quantum error correction

Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
1 vote
0 answers
61 views

Gate definitions for quantum random access codes

I would like to know how the gates are defined in quantum random access codes? Consider the $2 \to 1$ code described in Lemma 3.1 of this paper. The section defines the encoding and decoding circuits. ...
27 votes
5 answers
9k 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 ...
6 votes
0 answers
136 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 ...
6 votes
1 answer
301 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 ...
3 votes
0 answers
108 views

In quantum money schemes, how is the list of serial numbers provided?

Public key quantum currency generally includes $k$ pairs ($S_\psi,\vert \psi\rangle)$ of classical information (bits) $S_\psi$ and quantum information (qubits) $\vert \psi\rangle$. In many examples,...
8 votes
1 answer
467 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 ...
17 votes
1 answer
506 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 ...
2 votes
1 answer
71 views

QPIP minimal client quantum capabilities

It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al: https://www.researchgate.net/publication/...
4 votes
0 answers
75 views

Hardness of ancilla free quantum circuit extraction from circuit with ancillas

Is there any known result regarding the hardness of the following problem: Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
12 votes
1 answer
315 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 ...
6 votes
1 answer
941 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,...
2 votes
1 answer
102 views

Quantum circuit simulation divergence in results

I'm learning about quantum computing in order to code a simulator. I tried the following circuit in Quirk And ran the same circuit using OPENQASM 2.0: Notice that the input is |11> in both cases, ...
15 votes
5 answers
2k 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 ...
2 votes
1 answer
144 views

Complement for joint POVMs?

I'm trying to relate some notions of set theory to POVMs. I firstly explain the scenario with set theory and then in the POVM setting. For some finite $N \in \mathbb{N}$, let $A_i$ and $B_i$ for $i=1,...
10 votes
0 answers
263 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 ...
21 votes
7 answers
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 ...
2 votes
1 answer
191 views

Computing 'Robustness of Magic' of $n$-bit W states

Question What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$? Background $W$ states are entangled ...
-2 votes
2 answers
268 views

How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?

Suppose that I have a normalized quantum state $\sum_n a_n |n\rangle$, is there a quantum operation/circuit so that I can get $\frac{1}{N} \sum_n e^{i a_n} |n\rangle$ at output? How?
15 votes
1 answer
2k 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, ...
8 votes
1 answer
1k 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. ...
2 votes
0 answers
31 views

Are there wholistic models of the universe in terms of Quantum Complexity?

Quantum Computers are an abstraction (a finite circuit of matrices + measurements) that captures the computability properties of local quantum devices. But is there a notion, akin to "computability", ...
2 votes
0 answers
84 views

Query complexity of quantum search with measuring oracle

Consider the following problem: Let $x\in X$ be a uniformly random value. Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the ...
1 vote
0 answers
81 views

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the ...
1 vote
0 answers
144 views

Connection between diamond norm and output purity norm

Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
4 votes
1 answer
753 views

Simulating quantum measurements by unitaries

I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] for instance: Often we will describe quantum circuits in a high-level ...
1 vote
1 answer
104 views

Finding a basis for quantum measurement with maximum distinguishability

I wish to find a basis state for the quantum measurement of two states which provides the maximum possible distinguishability. In this example let's say we wish to find the best basis ($|\psi\rangle$) ...
8 votes
1 answer
215 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 ...
2 votes
1 answer
260 views

Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
1 vote
0 answers
90 views

How to simulate the quantum measurement of a quantum state in Quantum Image

I'm trying to implement (simulate) the Novel Enhanced Quantum Representation (NEQR), which is one of the quantum image representation models, but i'm stuck in the measurement part. In other words i ...
2 votes
0 answers
114 views

Cutting edge of quantum error correction

Often I find myself needing to know the best error correcting code for a certain quantum scenario. For example, suppose my logical systems are 3-dimensional; then what's the most efficient encoding to ...
4 votes
0 answers
107 views

Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?

Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi. In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
1 vote
0 answers
185 views

Two definitions of $QMA$

In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA. In Quantum Computational Complexity, John Watrous defines the class QMA ...
2 votes
1 answer
100 views

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said: The encoding disallows compression: it is not possible to work with encoding schemes that allow for ...
2 votes
1 answer
238 views

Quantum GCD circuit: On reversibility and clearing ancillae

Originally posted on PHYS, however, obviously it has more to do with CS I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my ...