Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
13 votes
1 answer
346 views

Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

Context. I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I ...
Niel de Beaudrap's user avatar
36 votes
2 answers
2k views

Consequences of $SAT \in BQP$

As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far: Quantum computers are not known to ...
Giorgio Camerani's user avatar
28 votes
1 answer
5k views

Shor's factoring algorithm help

I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm. Given an $N$ we want to factor, we choose a random $x$ which has order $r$. The first step involves ...
Callum's user avatar
  • 283
10 votes
4 answers
760 views

Bounding the gap between quantum and deterministic query complexity

Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, ...
Artem Kaznatcheev's user avatar
-7 votes
1 answer
456 views

Duality computers

There is a lot on the internet about quantum computers and how they could factor integers. However, there is a type of computer which also uses the principles of quantum mechanics, which can be used ...
Craig Feinstein's user avatar
10 votes
1 answer
501 views

Span programs, witness size, and certificate complexity

A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (...
Artem Kaznatcheev's user avatar
10 votes
3 answers
605 views

Interactive Proofs via Postselection?

Define the computational model MPostBQP to be identical to PostBQP except we allow polynomially many qubit measurements before the post-selection and final measurement. Can we give any evidence ...
Shaun Harker's user avatar
9 votes
2 answers
265 views

Polynomial algorithms for UPB (Unextendable Product Bases)

Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n ...
Marcin Kotowski's user avatar
1 vote
2 answers
365 views

Quantum evolutions

I was reading Quantum Computation Explained to my Mother. While considering the following problem: Problem 1 Suppose we are given a mysterious boolean operator F (a black box) which takes one ...
Casebash's user avatar
  • 475
7 votes
2 answers
591 views

Quantum query complexity and certificate complexity

A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum ...
Artem Kaznatcheev's user avatar
2 votes
2 answers
400 views

Time-entanglement phenomenon

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know). The general notion of algorithm is model of ...
kakaz's user avatar
  • 208
17 votes
2 answers
469 views

Is PARITY in QAC_0 (if that even makes sense)

As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in fact const-dept circuits require EXP number of gates. What about QUANTUM circuits? a) Can PARITY be done with a ...
Bill GASARCH's user avatar
9 votes
1 answer
858 views

Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
Marcos Villagra's user avatar
26 votes
5 answers
9k 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 ...
Joe Fitzsimons's user avatar
-3 votes
2 answers
536 views

Understanding function controlled NOT gate

...
Pratik Deoghare's user avatar
3 votes
1 answer
287 views

Background Required to understand Quantum Monte Carlo techniques?

I'm trying to decide whether or not to do a project for a professor. The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project)...
Elliot JJ's user avatar
  • 745
21 votes
3 answers
1k views

Is there a Quantum equivalent of the Time hierarchy theorem ?

My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965. I wanted to know then if there was anything similar for Quantum Computing. Also, if not ...
Zelah 02's user avatar
  • 1,578
15 votes
2 answers
1k views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
Artem Kaznatcheev's user avatar
1 vote
0 answers
283 views

Separating the QIP hierarchy

Background: I'm a CS grad student. I've taken a course on computational complexity. Question: Can you suggest an introductory book on quantum computation, especially regarding the details of ...
Zirui Wang's user avatar
32 votes
2 answers
2k views

NP-intermediate problems with efficient quantum solutions

Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) ...
Huck Bennett's user avatar
  • 4,868
26 votes
1 answer
581 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 ...
Gil Kalai's user avatar
  • 6,023
12 votes
2 answers
801 views

What is the Relationship between QMA and AM?

I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$. I was surprised about this ...
Zelah 02's user avatar
  • 1,578
23 votes
2 answers
1k views

Are there descriptive complexity representations of quantum complexity classes?

The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in. Descriptive complexity theorists, such as Immerman and Fagin, have ...
user avatar
35 votes
1 answer
2k views

$BQP$ vs $QMA$?

The central problem of complexity theory is arguably $P$ vs $NP$. However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a ...
Anthony Leverrier's user avatar
13 votes
1 answer
5k views

Clifford group quantum operations and classical computation

The Clifford group of quantum operators is generated by the quantum operations: Controlled-Z, Hadamard, and Phase ($= |0\rangle\langle0| + i |1\rangle\langle1|$). A circuit composed only of these ...
Antonio Valerio Miceli-Barone's user avatar
9 votes
2 answers
445 views

The complexity of Area-lawed Hamiltonians

I have recently thought about "importing" some physics-related question into quantum CS: The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some ...
user avatar
20 votes
2 answers
1k views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
S Huntsman's user avatar
31 votes
2 answers
5k views

Quantum matrix multiplication?

It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model? Do we have any intuition that we can beat ...
Henry Yuen's user avatar
  • 3,788
26 votes
1 answer
2k views

How does the BosonSampling paper avoid easy classes of complex matrices?

In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the ...
András Salamon's user avatar
10 votes
1 answer
264 views

Dependent corrections in measurement-based Universal Blind Quantum Computation

In Universal Blind Quantum Computation the autors describe a measurement-based protocol which allows an almost classical user to perform arbitrary computations on a quantum server without revealing ...
Antonio Valerio Miceli-Barone's user avatar
9 votes
2 answers
985 views

Quantum PCP and hardness of simulating of Hamiltonians

I have a few questions about Quantum PCP conjecture: What is the statement of the quantum PCP conjecture? What implications would Quantum PCP theorem have for simulating of Hamiltonians? Is it ...
user avatar
22 votes
1 answer
871 views

How much computational power fits into a cubic centimeter?

This question is a followup on the question about DNA algorithms asked by Aadita Mehra. In comments there, Joe Fitzsimmons said, in part: [T]he radius of the system must scale proportionately to ...
Aaron Sterling's user avatar
18 votes
4 answers
981 views

If P = BQP, does this imply that PSPACE (= IP) = AM?

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking... I wondered what if Quantum Computers ...
Zelah 02's user avatar
  • 1,578
7 votes
2 answers
446 views

Energy cost of adiabatic quantum computation

I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic. In Adiabatic Quantum Computation is Equivalent ...
Antonio Valerio Miceli-Barone's user avatar
21 votes
7 answers
28k views

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...
Vincent Russo's user avatar
47 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 ...
Joe Fitzsimons's user avatar
9 votes
2 answers
788 views

Understanding QMA

This question comes out of an answer Joe Fitzsimons gave to a different question. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that ...
Suresh Venkat's user avatar
13 votes
2 answers
690 views

One-shot quantum hitting times

In the paper Quantum Random Walks Hit Exponentially Faster (arXiv:quant-ph/0205083) Kempe gives a notion of hitting time for quantum walks (in the hypercube) that is not very popular in the quantum ...
Marcos Villagra's user avatar
12 votes
2 answers
3k views

Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

I believe the answer to this question is well-known; but, unfortunately, I don't know. In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the ...
Jeremy Yan's user avatar
28 votes
2 answers
1k views

Approximate counting problem capturing BQP

In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say). Is ...
Manu's user avatar
  • 7,639
24 votes
3 answers
1k views

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Jason's user avatar
  • 241
11 votes
7 answers
2k views

Quantum Computation - Postulates of QM

I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book. I wanted to ask if anyone could try finding time to help me with whats going on with the ...
Akash Kumar's user avatar
  • 1,973
24 votes
3 answers
930 views

Can we quantify the "degree of quantumness" in a quantum algorithm ?

Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-...
Suresh Venkat's user avatar
20 votes
2 answers
1k views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
Marcos Villagra's user avatar
4 votes
6 answers
6k views

Ternary (and beyond) computation and quantum computing?

Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved. I have always thought that having more states could improve computing ...
Shane's user avatar
  • 2,233
5 votes
0 answers
614 views

Learning quantum CS [duplicate]

Possible Duplicate: What is the quantum computational model? What is the best way to study quantum branch of CS for the person with rather advanced background in classical CS? Does one need to ...
16 votes
6 answers
9k views

Quantum computing project ideas

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?
Deyaa's user avatar
  • 544
32 votes
11 answers
2k views

What is the quantum computational model?

I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the ...
Casebash's user avatar
  • 475
20 votes
4 answers
817 views

Is there an equivalent to derandomization for quantum algorithms?

With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed ...
Alexandre Passos's user avatar
25 votes
3 answers
1k views

Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
Suresh Venkat's user avatar

1
5 6 7
8
9