Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
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.
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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'...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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>$. ...
user avatar
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?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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}$ ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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?$$
user avatar
  • 12.5k

1
2 3 4 5
8