Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
376
questions
1
vote
0
answers
66
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
22
votes
2
answers
7k
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 ...
- 11
7
votes
0
answers
120
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
518
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
2
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 ...
- 23.5k
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
67
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
159
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
7
votes
3
answers
413
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 ...
- 960
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 ...
5
votes
0
answers
283
views
Quantum computer versus Random 3-SAT?
It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-...
- 540
5
votes
0
answers
121
views
Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?
One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
- 540
5
votes
0
answers
176
views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example this blog post by Scott Aaronson and this article in Quantum Magazine).
What are some problems that are currently ...
- 540
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 ...
- 540
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 ...
15
votes
0
answers
117
views
Lower bounds for quantum circuits using the geodesic framework [duplicate]
Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance ...
- 540
39
votes
2
answers
5k
views
Do any quantum algorithms improve on classical SAT?
Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )
For comparison, using Grover's algorithm on a quantum ...
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
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
26
votes
5
answers
874
views
Universal sets of gates for SU(3)?
In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an ...
CommunityBot
- 1
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 ...
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
9
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 ...
- 6,888
3
votes
3
answers
167
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 ...
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 ...
- 26.3k
8
votes
1
answer
153
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
46
votes
17
answers
4k
views
Physics results in TCS?
It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are
Quantum computation
...
- 543
4
votes
1
answer
135
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 ...
- 193
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 ...
- 23.5k
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
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-...
- 1,986
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
21
votes
2
answers
966
views
PPAD and Quantum
Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
- 738
-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 ...
- 177
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
4
votes
2
answers
1k
views
Continued Fraction Algorithm in Shor's Algorithm
I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.
We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies
\begin{...
- 81
23
votes
5
answers
7k
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 ...
- 11
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 ...
- 814
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 ...
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.
...
- 822
1
vote
0
answers
95
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