Questions tagged [quantum-information]
Theoretical issues related to the quantum treatment of information
113
questions
0
votes
0answers
40 views
Hidden subgroup problems in a tower of subgroups
Let $H$ be a hidden subgroup of $G_1$ that is indistinguishable from subgroup $H^{\prime}$ by quantum Fourier sampling. Now take a larger group $G_2$ such that it contains $G_1$. Now if I do quantum ...
1
vote
1answer
58 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/...
3
votes
0answers
59 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 ...
10
votes
1answer
224 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 ...
1
vote
1answer
82 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, ...
9
votes
0answers
231 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 ...
1
vote
1answer
137 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,...
2
votes
1answer
87 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 ...
12
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, ...
1
vote
0answers
113 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 ...
1
vote
0answers
26 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", ...
1
vote
0answers
66 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
0answers
62 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 ...
-2
votes
2answers
252 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?
1
vote
0answers
123 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 ...
13
votes
1answer
4k 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 ...
2
votes
1answer
337 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
1answer
80 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
1answer
186 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
1answer
161 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
0answers
80 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
0answers
98 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
0answers
98 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
0answers
110 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
1answer
88 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
1answer
1k views
Addition on a quantum computer
From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers.
For a simple arithmetic operation such as a+b+c+d where ...
3
votes
2answers
348 views
When is a non-unitary quantum system only theoretical?
Suppose we construct a non-unitary quantum system α in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates ...
0
votes
1answer
97 views
How are new probabilities computed when simulating measurement on a set of qubits?
Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure:
|000> -> a
|001> -> b
|010> -> c
|011> -> d
|100> -> e
|101> -> f
|...
0
votes
1answer
50 views
What are the general classes of measured systems
Imagine there is a class of system such that a measurement can be performed on an exemplar of this class, each measurement producing 1 bit of information. There are no limitation on how many times the ...
7
votes
1answer
866 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.
...
1
vote
1answer
75 views
Can a measurement commuting with the stabilizer of a state disturb the state?
In Nielsen and Chuang's "Quantum Computation and Quantum Information", Section 10.5.3, the authors claim the following:
With a system in state $|\psi\rangle$ with stabilizer $g_1,...,g_n$, if a ...
4
votes
1answer
348 views
theorems for universal set of quantum gates for SU(d)
It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a ...
4
votes
1answer
69 views
Is it possible to MAC a quantum state with a classical key under reasonable assumption?
Assume that classical one-way functions secure against quantum adversaries exist. Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that:
...
2
votes
1answer
95 views
Is it possible to encrypt quantum states under reasonable assumptions?
Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can ...
2
votes
1answer
179 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 ...
1
vote
1answer
73 views
How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?
In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial ...
4
votes
2answers
129 views
Is there any hidden subgroup of a symmetric group which can be efficiently determined?
There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum ...
2
votes
0answers
96 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 ...
0
votes
2answers
112 views
Entropy inequality of joint von Neumann entropy given some marginal inequalities
Assume that I have a pure, multipartite state $\omega_{ABCD}$ and a unitary $U(\omega_{ABCD})=\tau_{ABCD}$. The effect of $U$ on $\omega$ results in
$$
S(\omega_B)<S(\tau_B)
$$
and
$$
S(\omega_A)&...
0
votes
1answer
86 views
Question about discarding the second register in the standard approach of hidden subgroup algorithm
My questions:
What does discarding the second register mean for the standard approach of hidden subgroup algorithm?
Why does discarding let the first register end up in a mixed state?
My ...
-3
votes
1answer
136 views
Dimension of the Fourier transform for $S_5$ [closed]
My question:
What is the dimension of the Fourier transform for $S_5$?
My effort:
The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
1
vote
0answers
53 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 ...
11
votes
1answer
215 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 ...
3
votes
0answers
61 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 ...
3
votes
1answer
285 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 ...
5
votes
1answer
136 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 ...
-7
votes
1answer
4k views
Travelling sales man with Quantum Computers [closed]
I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
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 ...
2
votes
0answers
94 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....
0
votes
0answers
29 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 ...
