Questions tagged [quantum-computing]
A computation model which relies on quantum-mechanic phenomena, such as entanglement and superposition. This generalizes the probabilistic model of computation.
265
questions
0
votes
0
answers
30
views
Evidence for or against the conjecture $QCMA\subseteq BQP^{NP}$
Is there some (complexity theoretic) argument for or against Quantum-classical Merlin Arthur
$$QCMA\subseteq BQP^{NP}?$$
I am aware of one (weak!) supporting argument for posing it as a conjecture.
...
- 141
3
votes
1
answer
329
views
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
Simon's problem is a computational problem used to demonstrate an oracle separation between BQP and BPP classes.
It is known that the minimum number of oracle calls to be made by the BQP machine is $\...
- 141
0
votes
1
answer
43
views
How to show $NP^{BQP} = QMA$?
I am currently reading the below document authored by @Lieuwe Vinkhuijzen.
In equation 2.1 (page 14 of this), the below equation is mentioned.
$${\Sigma}_1^{BQP} =NP^{BQP}= QMA$$
$NP$, $BQP$, and $QMA$...
- 141
3
votes
1
answer
47
views
Are Quantum algorithms probing the oracle?
Considering Deutsch–Jozsa algorithm
problem statement, of not being able to recognize "constant functions" from "balanced functions" on single call conventionally is clear to me...
...
- 33
3
votes
0
answers
30
views
Good book on (Quantum) Complexity and Computability Theories to start learning the theorem $MIP^* = RE$ as an operator algebraist
I am looking for some greatest references that could help me understand the theorem $MIP^* = RE$ ($MIP*=RE$) step by step. The paper (The Connes Embedding Problem: A guided tour) covers various ...
4
votes
0
answers
54
views
The Hidden Subgroup Problem under different mappings
The Hidden Subgroup Problem (HSP) is an extremely prevalent problem in quantum computation, especially for factorization in Shor’s algorithm.
The problem is stated
Given an oracle for some function, $...
- 41
1
vote
0
answers
38
views
Is the HSP with the symmetric group exactly equivalent to the Graph Isomorphism problem?
It is well known that an algorithm to solve the Hidden Subgroup Problem (HSP) with the symmetric group can solve the Graph isomorphism problem.
But is this true in reverse? Will an algorithm for graph ...
- 327
1
vote
0
answers
42
views
Is Quantum Search (SAT with only oracle access) NP-hard (and not NP-complete)?
Quantum search differs from the standard boolean SAT as it is restricted to only oracle calls to a circuit (or CNF formula). Where SAT gives us the structure of a formula (however loosely defined that ...
- 253
3
votes
1
answer
200
views
Are quantum computer strictly "faster" than any massively parallel computer in terms of computational complexity?
I've seen that quantum computing calculations have their own complexity classes https://en.wikipedia.org/wiki/Quantum_complexity_theory, namely BQP and QMA.
I've heard that this would beat any ...
- 170
2
votes
0
answers
43
views
Quantum search with input as a classical circuit
Grover's algorithm assumes $U_f$ computing a function $f$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $f$ is given. So let's assume a reversible circuit, $C ...
- 253
1
vote
1
answer
44
views
Representing classical circuits with quantum gates
Many problems in computer science input boolean circuits to problems.
Just as a toy example, let's define the below problem to be called $A$:
Given a polynomial depth circuit with $N$ bits of output, ...
- 253
1
vote
1
answer
45
views
Making statements about quantum complexity theory
It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes.
The fallacy is in ...
- 11
-1
votes
1
answer
63
views
Does quantum computing imply LPO?
The binary expansion of a given real number can be encoded as an amplitude using the inverse QPE. Together with Amplitude Amplification, I wonder if this could indicate that the (some weakened?) ...
- 101
0
votes
1
answer
62
views
Quantum Turing machine
Is there a formal definition of a 'Quantum Turing machine'? I am mainly interested in how the tape position would move.
https://en.wikipedia.org/wiki/Turing_machine
https://en.wikipedia.org/wiki/...
- 103
2
votes
1
answer
76
views
Why doesn't the Deutsch Jozsa algorithm on a classical computer show P != BPP?
I recently saw this answer on a question in the Quantum Computing SE. The answer demonstrated how we can probabilistically find the answer to the Deutsch Jozsa problem on a PTM in $O(1)$ time, with an ...
- 253
0
votes
0
answers
28
views
Quantum algorithms speedup illustration
I know that to illustrate speed-up advantage of Grover's algorithm we can apply "square root": if the brute force search takes 100 hours, Grover's quantum search algorithm should take about ...
- 1
4
votes
0
answers
53
views
Are there any probabilistic models of computation that can strongly simulate themselves?
I was reading this question over on the quantum computation stackexchange, and the top answer stated that you can't (strongly) simulate even a probabilistic turing machine, on itself. I was just ...
- 253
0
votes
0
answers
41
views
are computer errors inevitable?
this is my First post,I apologize for my ignorance.
The question is:
Could a programmer (human or Ai) with all the computing power and infinite time create a simulation of a world with our same laws ...
1
vote
1
answer
60
views
What is different between two classes are 'incomparable' or two classes are 'not equal'?
Arora and Barak states (p. 230) the following:
What is the relation between $BQP$ and $NP$? It seems that quantum computers only offer a quadratic speedup (using Grover’s search) on $NP$-complete ...
- 749
2
votes
0
answers
76
views
Quantum Boolean SAT algorithm?
Is there a quantum SAT algorithm, a quantum analogue of the DPLL or CDCL algorithms?
Note: I'm not looking for the quantum analogue of the Boolean satisfiability problem (though that would be ...
- 154
3
votes
1
answer
62
views
SAT and #SAT in Quantum
Let us look at the two questions that are NP-complete for a classical computer:
Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT).
...
- 317
2
votes
1
answer
96
views
What would be the conseuqences of BQP = NEXPTIME?
On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly ...
- 239
1
vote
1
answer
51
views
Confusion about whats being processed in a quantum computer
Please correct me if im wrong but this is how I think quantum computers work.
Say we have a q-bit. The q-bit is put through a quantum gate to put it into a superposition and manipulate its ...
- 45
3
votes
1
answer
94
views
What happens if we change $\mathcal{BQP}$ to allow quantum bits, but not quantum gates?
In the definition of the class $\mathcal{BQP}$ found in textbooks we (as the circuit builders) have access to an unlimited number of deterministic zero-initialized qubits and to a finite set of ...
- 478
1
vote
0
answers
71
views
Is quantum computing a serious usable instrument for the IT industry?
Following this latest and very exciting research object I can't find till now a usable computer. By computer I understand a definitive switchable Hardware.
I would like to call actual "quantum ...
3
votes
1
answer
331
views
What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?
Shor's algorithm uses the Quantum Fourier Transform to find the period the function a^x mod N with "a" being a constant integer less than N and N being a ...
0
votes
1
answer
65
views
Is it possible to use a quantum computer simulation to perform a cyber attack?
Is it possible to use a quantum computer and or a simulation to perform a cyber attack on classic computers? This is part of a research objective I'm trying to figure out.
2
votes
1
answer
123
views
Why is CNOT the only non-trivial reversible gate for two input bits?
The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function:
$$
00 \to 00 \\ 01 \to 01 \\ 10 \to ...
- 21
1
vote
4
answers
80
views
Can quantum computers be modelled as a classical computer with access to an oracle?
Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.
and this is because quantum computers can do a fourier transform on $n$ qubits in $O(n^2)$ time as ...
- 91
0
votes
1
answer
213
views
How will Big O be with quantum computers?
I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change ...
- 1
1
vote
1
answer
48
views
What is the "formula" for "any cipher can be deciphered by a quantum computer"?
There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.
P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
- 503
4
votes
1
answer
171
views
Is there a concept of probabilistic quantum computers?
Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.
Accordingly a Quora answer
Quantum ...
- 503
2
votes
3
answers
106
views
What is the computer science interpretation of a qubit?
I am a CS major trying to decipher quantum computing. I have done some elementary study on qubits and I always seem to get lost at the "infinitely many" states that the qubit can have. And I ...
Hammad Mansoor
4
votes
1
answer
470
views
Why are complex numbers needed to define qubits?
I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view,...
- 239
3
votes
1
answer
121
views
How do two H gates act on two entangled qubits?
In this circuit, if the two qubits are initialized at state 0, then after the oracle they are entangled and in the state:
$$\frac{1}{2} (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$
My question is, ...
- 31
2
votes
0
answers
27
views
Special Properties for Oracles in HSP
Let $(G,+)$ be an abelian group, $X$ a finite set (of "colors"), and $f:G \to X$ a function such that there exists a subgroup $H<G$ for which $f$ separates cosets of $H$, i.e. $\forall a,...
- 742
0
votes
1
answer
27
views
Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation
The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$,
The reason for ...
- 151
1
vote
0
answers
69
views
BPP and BQP: Optimization Versions?
For optimization problems, I found complexity classes analog to some classes for decision problems, e.g. PO and NPO, mirroring P and NP for decision problems in the sense that optimization problems in ...
- 123
2
votes
0
answers
31
views
Generalizing Quantum Computation
When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to ...
- 375
6
votes
1
answer
978
views
Can quantum computing help solve NP-Complete problems?
i was just wondering if quantum computing has done any good so far in solving NP complete problems.
I am aware that quantum computing does solve some NP problems which are classically hard in ...
- 163
0
votes
3
answers
1k
views
What are analog and digital in computer science?
I once thought that any analog computer is any computer which "doesn't need electrical current to work".
I once thought that any digital computer is any computer which "does indeed need ...
- 3
3
votes
1
answer
177
views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP?
If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
- 356
5
votes
1
answer
148
views
Factoring algorithms after number field sieves
It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. ...
- 1,000
1
vote
0
answers
38
views
What is the simplest quantum algorithm to visualize a quantum computation?
I'm interested to visualize how a simple quantum computation can be done, step by step. Can you help me?
I need any simple example of how qubits can be used to make a computation.
- 11
5
votes
0
answers
602
views
Data structures for quantum computers
In classical computers we have List,Queue,Tree & etc data structures, since classical computers using 1's & 0's on those data structures. Then what happens when it comes to quantum computers,
...
- 151
5
votes
1
answer
145
views
Is there a complexity class QPP?
The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
- 1,146
1
vote
0
answers
26
views
Why are MM-1QFA strictly more powerful than MO-1QFA?
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); both ...
- 11
1
vote
2
answers
275
views
Can neural network process randomness?
So the question is : Is it theoretically possible to feed a neural network with some random values to expect an output since randomness is a lack of knowledge in most case.
For this question, I've ...
- 19
3
votes
1
answer
155
views
Can quantum computers really compute a vast number of possible solutions simultaneously?
This link says
They are not constrained to stepwise calculations but, rather, can
compute a vast number of possible solutions simultaneously—and at a
speed that is far beyond anything we can ...
- 209
2
votes
1
answer
605
views
Understanding the state vector in Quantum Computing
I have just started to learn QC. It is said that
The quantum state of $N$ qubits can be expressed as a vector in a space
of dimension $2^N$
If there is $1$ qubit then we have two possible state ...
- 209