Skip to main content

Questions tagged [quantum-information]

Theoretical issues related to the quantum treatment of information

33 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 votes
0 answers
262 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 ...
Greenstick's user avatar
10 votes
0 answers
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 ...
Joe Fitzsimons's user avatar
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 ...
Nav89's user avatar
  • 209
9 votes
0 answers
115 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 ...
Niel de Beaudrap's user avatar
8 votes
0 answers
358 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, ...
Antonio Valerio Miceli-Barone's user avatar
7 votes
0 answers
69 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 ...
W. J. Zeng's user avatar
7 votes
0 answers
281 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 '...
Omar Shehab's user avatar
6 votes
0 answers
135 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 ...
bean's user avatar
  • 161
6 votes
0 answers
182 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 ...
Omar Shehab's user avatar
5 votes
0 answers
192 views

Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?

This question continues from the previous question where I mistakenly asked a question that is too general. In quantum communication complexity, we always assume that Alice and Bob have unlimited ...
Danu's user avatar
  • 763
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 ...
John's user avatar
  • 141
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 ...
Omar Shehab's user avatar
4 votes
0 answers
79 views

Does simulating chiral gauge theories lie within BQP?

In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
CS physicist's user avatar
4 votes
0 answers
108 views

Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
Henry Yuen's user avatar
  • 3,798
3 votes
0 answers
100 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 ...
AngryLion's user avatar
  • 173
3 votes
0 answers
107 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,...
Mark S's user avatar
  • 1,083
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", ...
petar's user avatar
  • 21
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 ...
Dominique Unruh's user avatar
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 ...
Jamie Vicary's user avatar
2 votes
0 answers
130 views

Why hidden subgroup problem is easy for very large subgroup?

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
Omar Shehab's user avatar
2 votes
0 answers
95 views

Proofs to verify quantum states without revealing their description

Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$ where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state. Assume the function is a one-to-one mapping....
Subhayan's user avatar
  • 831
2 votes
0 answers
56 views

How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?

I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says, Since ...
Omar Shehab's user avatar
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\...
Yang's user avatar
  • 11
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 ...
Julio César JX's user avatar
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. ...
Omar Shehab's user avatar
1 vote
0 answers
80 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 ...
Samuel Schlesinger's user avatar
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 ...
anurag anshu's user avatar
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 ...
Abdalla Essam Ali's user avatar
1 vote
0 answers
184 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 ...
Omar Shehab's user avatar
1 vote
0 answers
58 views

First register in the hidden subgroup representations of Simon's and graph isomorphism problems

The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
Omar Shehab's user avatar
0 votes
0 answers
56 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 ...
James Bowery's user avatar
0 votes
0 answers
33 views

Hardness of finding similar (quantum) states

Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce ...
Subhayan's user avatar
  • 831
0 votes
0 answers
156 views

The quantum capacity of a trace-decreasing CP map

Assume a qubit quantum channel (trace-preserving CP (==completely positive) map) $\mathcal{N}:C^2\to C^2$ whose quantum capacity is known. Now I construct a new channel $\mathcal{M}:C^2\to C^{2+n}$ ...
user119381's user avatar