Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
377
questions
0
votes
0
answers
20
views
Strong/weak Fourier sampling for abelian hidden subgroup in non-abelian ambient group?
Is there any known results for quantum hidden subgroup algorithms (weak or strong Fourier sampling) to determine hidden abelian subgroup within non-abelian ambient group? Thanks.
- 997
1
vote
0
answers
67
views
Survey of Quantum Algorithms similar to Montanaro's from 2015
The survey https://arxiv.org/abs/1511.04206 by Montanaro is very nice in terms of giving a bird's eye view, which is very useful. As the author states in the abstract
Here we briefly survey some ...
- 1,986
7
votes
0
answers
121
views
Computing permanents when we are promised that the value of the permanent is large
Suppose you are given an $n$ by $m$ real matrix (or even complex matrix) with orthonormal rows. ($m=poly(n)$, say $m=n^2$.) For an $n$-tuples of columns (with repetitions) from M we consider the ...
- 5,983
13
votes
0
answers
520
views
New quantum algorithm for approximating permanent
Joonsuk Huh uploaded a paper "A fast quantum algorithm for computing matrix permanent
" on arxiv, which claims a polynomial-time algorithm approximating the permanent of an arbitrary matrix ...
- 261
0
votes
0
answers
61
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 ...
- 101
1
vote
0
answers
38
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\...
- 11
2
votes
0
answers
68
views
Relationship b/w $QMA$ and $QCMA$
I was trying to read and understand about the complexity classes $QMA$ and $QCMA$:
$QMA$ is defined as the class with the set of problem such that, given a quantum certificate for any problem, its ...
- 294
2
votes
0
answers
160
views
$NP=QMA$'s impact on $BPP$ vs $BQP$ problem
$\mathit{BPP}$ vs $\mathit{NP}$ and $\mathit{BQP}$ vs $\mathit{QMA}$ are two problems that are (in spirit, for classical and quantum computers respectively) similar and both are open. Moreover, we don'...
- 801
1
vote
0
answers
45
views
Weak simulation of Clifford circuits
Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the ...
0
votes
0
answers
101
views
What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?
The Question:
I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we ...
- 109
3
votes
0
answers
65
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 ...
- 153
1
vote
0
answers
93
views
Input length and calculation time to simulate a quantum measurement
Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. ...
0
votes
0
answers
58
views
Number of composite factors as a function of the number of bits of an integer
Is there a standard formula to calculate the number of composite factors using the number of bits of an integer?
- 997
1
vote
0
answers
33
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 ...
7
votes
3
answers
414
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 ...
- 199
2
votes
0
answers
44
views
What is known about the stabilizer rank of this simple state?
Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$,
$$ |\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$
What is known or conjectured about the stabilizer ...
- 1,704
3
votes
3
answers
168
views
The complexity of LH with constant gap
Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
- 91
1
vote
1
answer
212
views
Pursuing Theoretical Computer Science after CS major
So I am currently a sophomore majoring in Computer Science. In the Data Structures course that I am currently studying, I studied the basics of complexity of a program and big O-notation, etc. That ...
- 19
1
vote
1
answer
120
views
Quantum complexity of TQBF with an untrusted oracle
This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics.
Let $L$ be the language of true, fully alternating totally quantified boolean formulas ...
- 3,221
7
votes
1
answer
170
views
Quantum complexity of TQBF
There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity. Is that also the best known bound for quantum algorithms / circuits?
Edit: As pointed out by Huck Bennett, in ...
- 3,221
8
votes
1
answer
154
views
What are the general direction and target question in the field of quantum error correction?
After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
- 387
4
votes
1
answer
136
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 ...
- 387
6
votes
1
answer
246
views
Are all computational models of quantum computing equivalent?
So the question was inspired by a seminar which presented the following models of quantum computing:
Quantum Computing with Photons
Quantum Computing with Rydberg atoms
Quantum Computing with trapped ...
- 684
1
vote
0
answers
53
views
Does the approximatibility of individual gates together with unitarity imply BPP=BQP
Suppose you can prove upper bounds on errors from approximating an individual quantum gate by randomly hashing the qubits of a circuit to a polylog number of qubits. (So, you prove a bound on how much ...
- 101
2
votes
0
answers
98
views
Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea) [closed]
To conform with the CS Theory SE crossposting rules, I've created a separate post for dequantizing Shor's algorithm (discussion on the Quantum Computing Stack Exchange was mostly about Shor's ...
- 101
1
vote
0
answers
59
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. ...
- 997
7
votes
0
answers
187
views
What is the complexity of estimating the number of paths between two vertices of a large graph?
Consider an $N\times N$ adjacency matrix $A$ of some large, $b$-sparse undirected graph $G$. The $(i,j)$ entry of $A^m$ counts the number of $m$-length paths between vertex $i$ and vertex $j$.
We let ...
- 822
-2
votes
1
answer
171
views
What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?
Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different.
What evidences are there that $PP$ is in $BQP$?
What evidences are there that $PP$ is not ...
- 12.5k
1
vote
0
answers
48
views
Non-rigid isomorphic structures
In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
- 387
1
vote
1
answer
154
views
On the paper "Quantum Computing Hamiltonian cycles"
The paper Quantum Computing Hamiltonian cycles claims:
An algorithm for quantum computing Hamiltonian cycles of simple,
cubic, bipartite graphs is discussed. It is shown that it is possible to
evolve ...
- 1,955
1
vote
1
answer
105
views
Google quantum supremacy experiment data
I don't know if this is the right place to ask.
Still, I vaguely remember that there was a desire expressed by some people in this community to get access to the data of the 53 qubit Google quantum ...
- 13
1
vote
0
answers
119
views
Quantum error correction and graph codes
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
- 387
1
vote
0
answers
96
views
Oracle separation between coNP and QMA implies oracle separation between NP and QMA
In [this] paper, Aaronson remarks (page 2, footnote) that:
From the BBBV lower bound for quantum search [6], one immediately
obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for ...
- 153
1
vote
1
answer
139
views
Diagonalization arguments for QMA type proof systems
Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
- 153
5
votes
1
answer
140
views
Is black box parallel quantum speedup ever nontrivial?
Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries.
Are there any oracle problems where quantum ...
- 3,221
6
votes
2
answers
266
views
Quantum evasiveness conjecture?
A property of simple $n$-vertex graphs is said to be evasive if its deterministic query complexity is exactly maximal, $\binom{n}{2}$ (that is, the best algorithm must query all $\binom{n}{2}$ ...
- 35.7k
6
votes
0
answers
131
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 ...
- 161
3
votes
1
answer
94
views
What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper
I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:
To the best of our knowledge, ...
- 193
3
votes
0
answers
93
views
Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? (Quantum automata)
While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
- 31
10
votes
0
answers
268
views
Does MIP* = RE algebrize?
Does the MIP* = RE result algebrize? (It doesn’t relativize, as noted here.)
If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?
- 3,221
0
votes
3
answers
269
views
What would be the next step after quantum computing? [closed]
Is their anything that would make Quantum computing obsolete in the future? I know a Matrioksha Brain is the most powerful theoretical computer; but it probably won’t ever be realized. Too large and ...
- 9
5
votes
1
answer
183
views
Complexity of finding automorphism group of code
What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for ...
- 387
5
votes
1
answer
242
views
Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?
This is another attempt to formalize my former question on the topic.
I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
- 13.5k
5
votes
1
answer
259
views
Witness verifiable quantum advantage
Update: A slightly different version of this question has been answered here.
As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
...
- 13.5k
8
votes
1
answer
440
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 ...
- 471
5
votes
1
answer
234
views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
- 529
1
vote
1
answer
142
views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? [closed]
Note: This has been cross-posted to Quantum Computing SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies ...
- 307
2
votes
0
answers
186
views
Quantum advantage beyond the black-box model
Question
Aaronson wrote in his thesis that
“essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
- 395
8
votes
3
answers
543
views
Is the wording of Google's QC Supremacy valid?
Quantum supremacy using a programmable superconducting processor was published today. Scott Aaronson posted a few weeks ago a post about this paper and it was clear we will see a Nature or Science ...
- 463
4
votes
1
answer
240
views
Results comparing BQP and NEXP
Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
- 12.5k