Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
-2
votes
0answers
96 views

A query regarding relation b/w complexity classes $NP$ and $BQP$ in case of collapse of $PH$?

Assuming if $PSPACE$ collapses to the class $NP^{NP}$ $\mathsf{\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P = PSPACE}$. Since $\mathsf{NP\subseteq NP^{NP}}$ and $\mathsf{BQP\subseteq QMA \subseteq PSPACE} \...
-1
votes
0answers
76 views

Open Problems in Quantum Complexity Theory (2021)

What are some open problems in quantum computing or complexity theory where a novice researcher could reasonably hope to make contributions with a few months of steady effort? I know this question has ...
1
vote
0answers
78 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
0answers
51 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?
0
votes
0answers
27 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 ...
3
votes
1answer
269 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 ...
1
vote
0answers
31 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 ...
4
votes
3answers
148 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 ...
1
vote
1answer
181 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 ...
0
votes
0answers
33 views

Which algorithm for linear programming is suitable for the context of quantum computing?

There are two major types of algorithms for linear programming : extreme point based, interior point based. Which will be suitable for quantum computing?
1
vote
1answer
105 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 ...
7
votes
1answer
150 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 ...
8
votes
1answer
112 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 ...
4
votes
1answer
101 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 ...
0
votes
0answers
21 views

Direct Diffie-Hellman by Shor's algorithm

Shor's algorithm appears to be capable of finding discrete logarithm even if the modulus is composite. Does the algorithm implicitly compute the Carmichael Lambda which goes in the exponent or somehow ...
6
votes
1answer
224 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 ...
0
votes
0answers
50 views

generalizations of hidden subgroup problem

Quantum Fourier Sampling tries to solve hidden subgroup problem which is defined via a map $f$ from group $\mathrm{G}$ to some set $X$ that separates cosets of sum unknown subgroup $\mathrm{H}$. $f(...
1
vote
0answers
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 ...
2
votes
0answers
96 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 ...
0
votes
0answers
53 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. ...
7
votes
0answers
166 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 ...
-2
votes
1answer
166 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
44 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 ...
1
vote
1answer
127 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
104 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
114 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
vote
0answers
84 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
130 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
1answer
127 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 ...
6
votes
2answers
218 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}$ ...
5
votes
0answers
124 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 ...
3
votes
1answer
89 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, ...
2
votes
0answers
71 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
259 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
252 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 ...
5
votes
1answer
174 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
239 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 (...
5
votes
1answer
252 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. ...
7
votes
1answer
432 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 ...
5
votes
1answer
229 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
140 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 ...
2
votes
0answers
161 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 ...
8
votes
3answers
537 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 ...
4
votes
1answer
230 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?$$
21
votes
2answers
893 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 ...
2
votes
0answers
86 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
153 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
334 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
80 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
66 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/...

1
2 3 4 5
8