1
$\begingroup$

Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits, where the language of each given minimal DFA is finite and it's alphabet is Σ={0,1} and all words/strings in all languages are in the same length equal to the given number of minimal DFAs?

Remember that minimal DFA is deterministic finite automaton that there is no possibility to delete any of it's states and change it's transitions function δ so the language accepted by this DFA is unchanged.

EDIT: According to what I read here

3yakuya says in his answer:

As far as we believe, a quantum Turing machine is able to simulate any quantum computer, and it is also equivalent to classical deterministic Turing machine in terms of computability.

I don't know why he/she uses the word "believe", I think that it is known fact, because quantum computers where designed to solve every problem correctly, so it should be possible for quantum computer to compute the minimal intersection DFA of numerous minimal DFAs correctly, i.e. this is a task that can be accomplished and computed by quantum computer.

3yakuya then says:

However, if we consider practical computability, things may look a bit different. Imagine a problem where we have a classical solution which runs with O(2n)O(2n) complexity. It is definitely solvable, but for any reasonable data size it will require massive amounts of operations. In practice, it will run for thousands of years, even on the fastest computers. Now imagine we have a quantum algorithm solving the same problem, but with O(n)O(n) complexity. Out of a sudden, exact same problem can be solved in minutes, which is very reasonable (especially compared to thousands of years).

If quantum computer runs the classical algorithm (that can also be run by deterministic turing machine) to compute the minimal intersection DFA, by first computing the product intersection DFA (not minimal) and then minimize it by using Hopcroft's algorithm, then this will take too much time for the quantum computer to finish and no one will wait until it is done, and the same is correct for deterministic turing machine, but if quantum computer runs quantum algorithm to compute the same thing, but much more efficiently than the classical algorithm (without computing products and calling any minimization algorithm), but getting the minimal intersection DFA more directly and quickly by quantum algorithm, which suppose to run only by quantum computer, but not by deterministic turing machine, then it is expected that the quantum computer running this quantum algorithm will finish much faster and at most polynomial time.

So until now there is hope, but after the first quote and before the second quote, 3yakuya said:

In other words, as far as we know the space of problems solvable by quantum computers is the same as space of problems solvable by classical computers.

That's really bad! Computing the minimal intersection DFA of numerous minimal DFAs is PSPACE-Complete problem! That means, the machine needs non-polynomial amount and quantity of memory to finish the computation!

The main reason that deterministic turing machine won't do that, because in reality, deterministic turing machine have finite tapes! Not infinite! For some large input, the turing machine (deterministic) won't have enough tape to write down the result, i.e. the minimal intersection DFA!

But I thought that "out of memory" problem can occur in classical computers, because their memory is a finite array of bits, where each bit has two states only: 0 and 1, so to describe larger object, the classical computer needs more memory, and in fact more bits, but quantum computer has qubits rather than bits, and single qubit suppose to have "infinitely" states, which are 0, 1 and the superpositions of 0 and 1. If so, quantum computer should have like "infinite memory", no? Out of memory expected to occur in classical computer, but not in quantum computers, so space problems for quantum computers suppose to be O(1), in contrast to classical computers, which is rarely O(1), but most of them are much worse than O(1). Maybe I misunderstand what really quantum computer is or 3yakuya is wrong in what he/she says?

If 3yakuya is right, then the answer to my question is NO, quantum computer won't be able to compute the minimal intersection DFA, because it will require non-polynomial number of qubits or something and that's too many.

Improve this question
$\endgroup$
9
  • $\begingroup$ Correct me if I am wrong. If I want intersection of 3 DFAs, I can find intersection of any two of them first and then intersect the 3rd with this intersection right? Similarly for 4,5,...DFAs. So cannot we say that we have a classical polynomial time ($\Theta(n)$) algorithm where $n$ is the number of DFAs? $\endgroup$
    – User Not Found
    Commented Jul 12, 2017 at 15:58
  • $\begingroup$ I said polynomial, not linear, I don't think that quantum computer is really going to finish computation in linear time, but if someone proves this, this going to be great, but this will be fine if it takes some polynomial time, i.e. theta(n^2) or theta(n^3)... And by the way, this doesn't matter in which order you compute the intersection of all minimal DFAs, you will eventually get the same minimal DFA, the quantum computer can just compute the intersection of the first two minimal DFAs, then third, then fourth and etc. There is another option to sort them all and extract from priority queue $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 12, 2017 at 16:09
  • $\begingroup$ The two minimal DFAs with the fewest states and compute their intersection and insert it to the priority queue. Repeat this process until the priority queue contains only 1 DFA, which suppose to be the output of the algorithm. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 12, 2017 at 16:13
  • $\begingroup$ So what I was saying was linear and even the algorithm you suggested they are all polynomial right? So where is the problem? $\endgroup$
    – User Not Found
    Commented Jul 12, 2017 at 16:20
  • $\begingroup$ This is a yes/no question, not describing a problem, I just want to know if it is possible for quantum computer to compute the minimal intersection DFA efficiently enough, i.e. polynomial in time and space. If so, I think that it will be possible to prove that quantum computers are as powerful as non-deterministic turing machines, and they can be used to solve every problem in NP in polynomial time, by solving a NP-Complete problem in polynomial time by using a quantum algorithm. That's all. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 12, 2017 at 16:47

1 Answer 1

Reset to default
2
$\begingroup$

No. The size of the minimal DFA for the intersection might be exponentially large. Therefore, no computer can compute it in polynomial time, not even a quantum computer -- it requires exponential time even to write down the answer. In particular, if you have $n$ languages, each of whose minimal DFA has size $m$, then the minimal DFA for their intersection can be as large as $\Theta(m^n)$. This is exponential in $n$.

Separately: it is known that $\mathbf{BQP} \subseteq \mathbf{PSPACE}$. it is generally believed/conjectured that $\mathbf{BQP} \subsetneq \mathbf{PSPACE}$ (i.e., it is a proper subset); if that is correct, then it follows that no PSPACE-complete problem can be solved by a quantum computer in polynomial time.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.