2
$\begingroup$

From quantum computation point of view, the complexity of a quantum state $|\psi\rangle$ can be defined as the the complexity of the quantum circuit that can generate the state $|\psi\rangle$ from an initial product state $|0000...0\rangle$.

Generally we can classify a general n-qubit state into two sets, a polynormial complexity set and an exponential complexity set w.r.t. the qubit number n.

We know to determine the complexity of a state is a hard problem, also the complexity is not linear since the linear combination of two 'simple' states can be 'complicated' or vise versa.

My question:

The state space is continuous, is there a clean/smooth border between these two sets? For me, this is analogous with the border between rational and non-rational numbers. But I have no idea about the structure of this border.

PS. Thanks to Norbert Schuch, now I noticed that it's really difficult to define the complexity of a state unless we mean a certain structured state such as the GHZ state of n-qubit.

If we define the state in such a way, then is it possible that if the state is polynomial or exponential can vibrate depending on the qubit number n? For example for an odd n, it may be generated by an algorithm/unitary operation with a polynomial complexity, but for an even n, it can only be a result of an exponential computation?

Improve this question
$\endgroup$
6
  • $\begingroup$ Complexity is an asymptotic concept (here, as we increase the dimension of the Hilbert space). This is in sharp contrast to rational vs. irrational numbers, which is defined on a given space. $\endgroup$
    – Norbert Schuch
    Commented Aug 19, 2017 at 9:28
  • $\begingroup$ @ Norbert Schuch Yes. I agree. But we can equivalently convert the state complexity problem into the algorithm complexity problem if we regard a n-qubit state as the solution of a certain quantum computation algorithm, or the ground state of a certain structured Hamiltonian defined on n qubits. $\endgroup$
    – XXDD
    Commented Aug 19, 2017 at 9:55
  • $\begingroup$ @John Forkosh Yes. It's easier to define the algorithmic complexity. But the problem is that there is no such a mapping between the algorithmic complexity and the state complexity (I was wrong in my last comment). In fact I am more interested in the state complexity when n goes to infinity. $\endgroup$
    – XXDD
    Commented Aug 19, 2017 at 9:59
  • $\begingroup$ Still I am more interested in the structure (pattern) of the entanglement in a n-qubit system when n goes to infinity. I have proposed this problem before, but got no response here. It seems that the entanglement pattern of a random/generic n-qubit state is very important to understand lots of problems including the blackhole dynamics and entanglement order in condensed matter. State complexity is just part of the generic state pattern. $\endgroup$
    – XXDD
    Commented Aug 19, 2017 at 10:02
  • $\begingroup$ @X.Dong Whether you express it as state complexity or circuit complexity: It is complexity, and it is an asymptotic concept. You won't get a sharp separation the same way you get it in the case of rational numbers. $\endgroup$
    – Norbert Schuch
    Commented Aug 19, 2017 at 10:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.