Quantum advantage in deciding NP-complete problems

DOI10.1007/S11128-023-03889-3MaRDI QIDQ2689786zbMATH OpenOpenAlexFDO

Authors Marius Nagy, Naya Nagy

Publication date 14 March 2023

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11128-023-03889-3

zbMATH Keywords

probabilityNP-completequantum state discriminationprojective measurementquantum advantagePOVM measurementdecision-version

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum measurement theory, state operations, state preparations (81P15) Quantum state tomography, quantum state discrimination (81P18)

Recommendations

• Solving NP-Complete Problems with Quantum Search
• scientific article; zbMATH DE number 1555956
• Strengths and Weaknesses of Quantum Computing
• New quantum algorithm solving the NP complete problem
• New quantum algorithm for studying NP-complete problems

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• A semidefinite programming approach to optimal unambiguous discrimination of quantum states
• Optimal distinction between non-orthogonal quantum states
• Optimal distinction between two non-orthogonal quantum states
• Optimum unambiguous discrimination of two mixed quantum states
• Quantum computation and quantum information. 10th anniversary edition
• Statistical decision theory for quantum systems
• Unambiguous discrimination between linearly independent quantum states.

Cited in

(7)

• Quantum advantage through the magic pentagram problem
• scientific article; zbMATH DE number 1530002 (Why is no real title available?)
• scientific article; zbMATH DE number 1555956 (Why is no real title available?)
• Quantum advantage with shallow circuits
• Characterization of quantum computable decision problems by state discrimination
• Solving NP-Complete Problems with Quantum Search
• Superlinear advantage for exact quantum algorithms

This page was built for publication: Quantum advantage in deciding NP-complete problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689786)