What is QMA?
The Class of Quantum Proof Systems is Quantum Merlin Arthur (QMA).
The quantum counterpart of the classical complexity class NP (Non-deterministic Polynomial time), Quantum Merlin Arthur (QMA), is a basic complexity class in quantum complexity theory. The idea of having a verifiable quantum proof for a decision problem is formalized by the QMA structure. The probabilistic complexity class MA (Merlin Arthur) is comparable to QMA as well.
The Roles and Proof System
The two main agents in the QMA framework are Arthur, the polynomial-time quantum verifier, and Merlin, the all-powerful but unreliable prover. Since Arthur belongs to the class BQP (Bounded-Error Quantum Polynomial Time), the verification procedure operates as a quantum algorithm in bounded polynomial time. It is Merlin’s responsibility to provide Arthur with evidence that a specified input string is a member of the relevant language.
Importantly, a polynomial-size quantum state, often called a quantum certificate or witness (expressed by qubits), is the proof in QMA. This quantum state and the input instance of the problem are sent to the verifier (Arthur), who has to choose whether to accept or reject the claim.
Also Read About Quantum Enhanced Markov Chain Monte Carlo MCMC Methods
Defining Completeness and Soundness
The QMA decision issues must meet stringent probability requirements, such as completeness and soundness.
- Completeness: There must be an ideal quantum proof from Merlin that persuades Arthur (the verifier) that the input instance is, in fact, a “YES” instance (i.e., the string is in the language) with a high probability. The verifier’s acceptance probability must exceed a predetermined constant if the input is in the language.
- Soundness: No matter what quantum state Merlin supplies, Arthur must reject with high probability if the input instance is a “NO” instance. The likelihood that Arthur will accept any quantum proof that the cunning enemy Merlin sends must be less than a predetermined constant.
Acceptance probabilities like two-thirds (for YES occurrences) and rejection probabilities like one-third (for NO instances) are commonly used in the conventional definition of QMA. If these constants are substituted by any other constants where the acceptance probability is higher than the rejection probability, the class is mathematically unaffected.
Robustness and Error Reduction
QMA is resilient to possible cheating efforts by Merlin. Error amplification techniques enable increasing the success probability to approach exponentially close to 1, while it is unclear if QMA stays the same if the acceptance chance for YES occurrences is required to be exactly 1.
Replicating the evidence and running the verifier several times while selecting a majority result is the basis for error reduction in classical complexity. However, an unknown quantum state cannot be replicated due to quantum mechanics (the no-cloning theorem). Requiring Merlin to provide several identical copies of the quantum proof state is the answer in QMA. The soundness property ensures Arthur rejects with high probability, even if Merlin tries to cheat by sending entangled states instead of independent copies when the input is a NO-instance.
Also Read About Quantum State Tomography (QST) Importance, Benefits & future
Relationship to Other Complexity Classes
Building on a number of important classical and quantum classes, QMA occupies a prominent place in the hierarchy of complexity classes.
- QMA also includes all of the P, NP, and BQP problems.
- The fact that MA is a part of QMA directly leads to the inclusion of NP in QMA. MA is contained in QMA since any randomized algorithm can be efficiently simulated by a quantum computer, and the verifier can make the quantum proof classical by measuring the qubits.
- As demonstrated by Kitaev and Watrous, QMA is also a part of PP (Probabilistic Polynomial Time), which is a part of PSPACE.
- In a comparable class called QCMA (Quantum Classical Merlin Arthur), the evidence needs to be a classical string, but the verifier is quantum. It is evident that QCMA is a part of QMA.
- QMA is a particular case of Quantum Interactive Polynomial time (QIP) in which the prover and the verifier exchange only one message, making it comparable to QIP(1).
QMA Complete Problems
- If a problem belongs to QMA and is QMA-hard (i.e., all QMA problems can be reduced to it), it is said to be QMA-complete.
- Identifying QMA-complete issues is crucial to comprehending the intrinsic difficulty of the class.
- The k-Local Hamiltonian Problem is the most well-known issue in QMA. The classical MAX-SAT or Constraint Satisfaction Problems have a quantum counterpart in this problem. It asks about a Hamiltonian’s ground state energy, or its smallest eigenvalue, and is motivated by physical principles.
- A sum of terms, each acting on a small number of (k) qubits, is used to express the Hamiltonian. This problem’s decision version asks if the ground state energy is above a threshold α or below a threshold β. For k higher than or equal to two, the k-Local Hamiltonian problem is known to be QMA-complete.
The consistency of local density matrices and variations of the local Hamiltonian problem, such as the pinned commuting and pinned stoquastic local Hamiltonian problems, are further issues that are regarded as QMA-complete or QMA-hard. The idea of “pinned” issues, in which one qubit is fixed in a specific state, demonstrates that these constrained Hamiltonian problems are also QMA-complete and raises challenging static questions regarding the ground-state features.
Also Read About IBM Qiskit Functions Templates Advances Quantum Research
