Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
355
questions
-2
votes
1answer
102 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 ...
1
vote
0answers
33 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 ...
3
votes
2answers
715 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{...
21
votes
5answers
6k 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 ...
1
vote
1answer
85 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
vote
1answer
94 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 ...
1
vote
0answers
58 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-...
22
votes
2answers
750 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 ...
4
votes
1answer
115 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 ...
0
votes
0answers
27 views
Must the cryptographic test for quantumness in [BCMVV18] use post-quantum Trapdoor Claw-Free Functions?
Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable computational quantumness based on a strengthening of trap-door claw-free functions (TCFs).
In the above scheme:
...
5
votes
1answer
235 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.
...
1
vote
0answers
22 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 ...
1
vote
1answer
106 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 ...
5
votes
0answers
115 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 ...
77
votes
8answers
42k views
What would a very simple quantum program look like?
In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first ...
6
votes
1answer
289 views
Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel
I am aware that quantum entanglement cannot increase the asymptotic capacity of a noiseless classical channel. However, can anyone provide some type of reference in the literature that contains a ...
6
votes
2answers
172 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}$ ...
20
votes
1answer
5k 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 ...
25
votes
1answer
521 views
Approximately sampling from convex polyhedrons with quantum computers
Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that ...
3
votes
1answer
78 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, ...
1
vote
1answer
224 views
Quantum Computing: project ideas
I'm an undergraduate computer science student and I'm currently taking a course in the field of quantum computing requiring projects. I've read already a huge number of articles but still cannot come ...
2
votes
0answers
67 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 ...
10
votes
0answers
228 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?
0
votes
3answers
243 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 ...
8
votes
3answers
530 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 ...
5
votes
1answer
133 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 ...
5
votes
1answer
232 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 (...
7
votes
1answer
396 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 ...
2
votes
0answers
128 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 ...
5
votes
1answer
216 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 ...
1
vote
1answer
128 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 ...
4
votes
1answer
206 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?$$
16
votes
1answer
410 views
Oracular separations between poly- and log-depth quantum circuits
The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory.
Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any ...
0
votes
0answers
43 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 ...
2
votes
0answers
78 views
Quantum security of cryptosystems
One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...
4
votes
1answer
146 views
Given a subset of of the hypercube and an affine transform of it, find the affine map
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some ...
7
votes
2answers
328 views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
0
votes
1answer
74 views
Grover's algorithm, M out of N, when M is large
The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries.
I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to ...
2
votes
1answer
62 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/...
8
votes
1answer
290 views
Is there any quantum analog of the VP vs. VNP problem?
From Wikipedia:
$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\mathsf{...
9
votes
3answers
491 views
Why exactly are complexity theorists interested in closed timelike curves?
Context:
There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which ...
2
votes
1answer
132 views
Lower bound on alternations needed in $BQP$ versus $PH$ result?
What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
11
votes
5answers
1k views
List of quantum-inspired algorithms
Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:
A quantum-inspired classical ...
1
vote
0answers
131 views
What can be some bachelor thesis ideas in Quantum random walks?
Note: Cross-posted on Quantum Computing Stack Exchange.
I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
11
votes
2answers
511 views
Notation for a Conditional Hamiltonian Evolution Operator
I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write
Next we apply the conditional Hamiltonian evolution $...
3
votes
1answer
220 views
String theory based computations
I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of ...
4
votes
0answers
91 views
Is there a universal gate set for classical probabilistic computing?
We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
4
votes
0answers
120 views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
1
vote
0answers
21 views
whether two sets of stabilizer generators are related by a Clifford circuit
I have two stabilizer models each specified with a given set of generators. Let's call the two generating sets $S_1$ and $S_2$. By stabilizer model, I mean putting the generators on unit cells of a ...
-1
votes
1answer
63 views
QMA definition of difference between probabilities intuition
I'm reading about the complexity classes related to quantum computation, currently I'm studying QMA class. A language is in QMA(c,s) if there exists a polynomial time verifier and polynomial $p(n)$ ...
