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.
271 questions
2
votes
0
answers
87
views
Does my understanding violate anything known about NP-intermediate classes and crypto?
I've been sort of thinking about $C^{poly}$ witnesses for a certain reason for several years and sort of weaker senses of reductions of problems in the back of my mind, but I just recently saw results ...
- 53
1
vote
0
answers
80
views
Understanding Reversibility of Quantum Computing in Proving Boolean Circuits as A Subcase of Quantum Circuits
I'm reading quantum computation in Arora and Barak, on page 215 they provide the Lemma 10.10 proving that quantum circuits can simulate boolean circuits.
Lemma 10.10 (Boolean circuits as a subcase of ...
- 637
2
votes
0
answers
94
views
How does quantum computing pseudocode look like?
In classical programming, pseudocode follows some informal but widely understood standards, focusing on clarity and abstraction while omitting low-level implementation details. However, quantum ...
0
votes
0
answers
66
views
Confused about a property of quantum registers
I'm trying to understand quantum registers. At present, I understand that a quantum register composed of $m$ qubits is a superposition of $2^m$ basic states, and is represented as a vector $\...
- 33
0
votes
0
answers
47
views
Linearity Condition on Quantum Operations
I'm trying to understand quantum operations. At present, I understand that a quantum register composed of $m$ qubits is a superposition of $2^m$ basic states, and is represented as a vector $\...
- 33
0
votes
0
answers
21
views
Is there a name for the complexity class for an oracle for matrix elements of arbitrary polynomial-size unitary circuits?
Suppose you had an oracle that could efficiently compute matrix elements (in the computational basis) $\langle x | C | y \rangle$ for arbitrary polynomial-size circuits $C$. Is there a name for the ...
- 1,184
0
votes
0
answers
33
views
LP duality for approximate bounded degree
$\begin{align*}
&\text{min } \epsilon \\
&|f(x) - \sum_{|S|\leq d} c_S \chi_S(x)| \leq \epsilon, \ \ \ x \in D \\
&|\sum_{|S| \leq d} c_S \chi_S(x)| \leq 1 + \epsilon, \ \ \ x \in \{-1,...
3
votes
1
answer
390
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 $\...
- 189
0
votes
1
answer
113
views
How to show $\mathsf{NP^{BQP} = QMA}$?
I was reading the document below, authored by @Lieuwe Vinkhuijzen.
In equation 2.1 (page 14 of this), the following equation is mentioned.
$$\mathsf{\Sigma_1^{BQP} =NP^{BQP}= QMA}$$
$\mathsf{NP}$, $\...
- 189
3
votes
1
answer
101
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
56
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
72
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
58
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
75
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 ...
- 263
3
votes
1
answer
345
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