Carview!

0 votes

0 answers

53 views

Maximally complex states

In terms of gate count, Haar random states are maximally complex. If we yet consider (mixed) states, how can we characterise states with maximal complexity?

user1577744

43

asked Jul 25 at 9:50

4 votes

1 answer

244 views

Complexity of finding a fixed-point of a unitary / eigenstate with eigenvalue 1?

Recently, while working on a problem I've been trying to solve I came across a formulation that requires me to find $|\phi\rangle$, such that $$U|\phi\rangle = |\phi\rangle$$ Of course this ...

Ramezzez

316

asked Jul 7 at 19:10

2 votes

1 answer

188 views

Complexity of checking if a circuit is deterministic or not?

Suppose I am given a list of gates for some circuit. I start with some fixed state, say $\vert 000..\rangle$, and measure the output in the computational basis. I want to know if the circuit is ...

user1936752

3,383

asked May 21 at 7:25

0 votes

0 answers

69 views

Relationship between a language and promise problem class

What is the relationship between $\textbf{precise-promiseQCMA}$ and $\textbf{precise-QCMA}$? Cross-posted on Theoretical Computer Science Stack Exchange. I was recently reading about precise ...

QuantumBeef

21

asked May 5 at 8:58

1 vote

2 answers

120 views

Is there a sign-problem when the wavefunction itself has positive and negative values, or is it only when the Hamiltonian has such entries?

Consider the following two problems: Let $A$ be an $s$-sparse $2^n\times 2^n$ Hermitian matrix with entries $A_{jk}$ in $\{0,1,-1\}$ both along the main diagonal and off the diagonal. Let $|\psi\...

Mark Spinelli

15.8k

asked Apr 28 at 13:12

1 vote

0 answers

66 views

Can problems about Perfect State Transfer ever be BQP-Complete?

I was watching a recent video by Krystal Guo on algebraic graph theory with a focus on Perfect State Transfer (PST) - which occurs on a graph $X$ having adjacency matrix $A(X)$ between vertices $u$ ...

Mark Spinelli

15.8k

asked Apr 6 at 14:33

4 votes

0 answers

123 views

Prepare a superposition with period gcd(A, B) in log depth

According to John Watrous, it's not known how to test coprimality in logarithmic depth. This is a special case of there being no known way to compute an n-bit gcd in less than $\Omega(n / \log n)$ ...

Craig Gidney

48.2k

asked Mar 29 at 18:35

1 vote

2 answers

176 views

Why Must We Remove Garbage for Interference Tests? Graph Isomorphism example

I am curious about quantum approaches to graph isomorphism and have encountered a recurring point: the necessity of cleaning up any garbage generated during state preparation. For example, take a look ...

tigerjack

588

asked Mar 15 at 16:07

1 vote

1 answer

103 views

Indistinguishability of mixed states

I have a question regarding indistinguishability of mixed states. Suppose I have two random variable (purely classical) $Y_0, Y_1 : \mathcal{R} \to \{0,1\}^n$ that are quantum computationally ...

kingoyster

111

asked Mar 13 at 12:35

1 vote

1 answer

145 views

Relationship between MIP*[$\log(n),O(1)$] and NP

MIP* is the multi-prover interactive proof system where provers can share arbitrary many entanglements. My question is what is the relationship between MIP*[$\log(n),O(1)$] and NP? MIP*[$\log(n),O(1)$]...

qmww987

385

asked Mar 10 at 14:20

3 votes

1 answer

91 views

Factoring and hardness of Factoring $\Rightarrow$ BQP $\neq$ BPP, or $\Rightarrow$ promise BQP $\neq$ promise BPP?

I know that BQP and promise BQP are often not distinguished, but what I don't understand is, does Shor algorithm (under the important assumption that factoring is hard) prove that: $BQP \ne BPP$, so ...

veit

33

asked Mar 6 at 23:21

3 votes

0 answers

50 views

Depth complexitiy of computing logical $T$ gate in the Toric Code

There are several known ways to compute the logical $T$ gates in the Toric Code, some of which are considered very efficient since, besides a preprocessing cost, require only constant depth of quantum ...

Dudu Ponar

470

asked Mar 2 at 7:46

1 vote

1 answer

78 views

Is there a metric or definition for how "quantum-friendly" a problem is?

I'm looking for a way to classify computational problems based on how suitable they are for quantum computers. Specifically, is there an established metric, definition, or framework that categorizes ...

user

111

asked Feb 20 at 9:25

0 votes

0 answers

74 views

One Shot Signature Security Proof

I was studying the paper (e-print) "One Shot Signatures and Applications to Hybrid Quantum/Classical Authentication." In it, the authors define "equivocal hashing" and provide a ...

woah

23

asked Feb 18 at 20:23

0 votes

1 answer

122 views

Dishonest Proofs in QMA

My question concerns the acceptance probability of dishonest proofs in the YES case of a QMA verification protocol. According to the canonical definition of QMA, the completeness condition requires ...

QuantumBeef

21

asked Feb 18 at 5:18

Stack Exchange Network

Questions tagged [complexity-theory]

Maximally complex states

Complexity of finding a fixed-point of a unitary / eigenstate with eigenvalue 1?

Complexity of checking if a circuit is deterministic or not?

Relationship between a language and promise problem class

Is there a sign-problem when the wavefunction itself has positive and negative values, or is it only when the Hamiltonian has such entries?

Can problems about Perfect State Transfer ever be BQP-Complete?

Prepare a superposition with period gcd(A, B) in log depth

Why Must We Remove Garbage for Interference Tests? Graph Isomorphism example

Indistinguishability of mixed states

Relationship between MIP*[$\log(n),O(1)$] and NP

Factoring and hardness of Factoring $\Rightarrow$ BQP $\neq$ BPP, or $\Rightarrow$ promise BQP $\neq$ promise BPP?

Depth complexitiy of computing logical $T$ gate in the Toric Code

Is there a metric or definition for how "quantum-friendly" a problem is?

One Shot Signature Security Proof

Dishonest Proofs in QMA

Hot Network Questions

Questions tagged [complexity-theory]

Related Tags