Renata Wong

Renata Wong


Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 March 2023 in Scientific Reports
Verified
Journal Article
Open access
PDF file
RWRenata Wong
Renata Wong
WCWeng-Long Chang
Weng-Long Chang
WCWen-Yu Chung
Wen-Yu Chung
Athanasios V. VasilakosAthanasios V. Vasilakos
Athanasios V. Vasilakos
A dominating set of a graph $$G = (V, E)$$ G = ( V , E ) is a subset U of its vertices V, such that any vertex of G is either in U, or has a neighbor in U. The dominating-set problem is to find a minimum dominating set in G. Dominating sets are of critical importance for various types of networks/graphs, and find therefore potential applications in many fields. Particularly, in the area of communication, dominating sets are prominently used in the efficient organization of large-scale wireless ad hoc and sensor networks. However, the dominating set problem is also a hard optimization problem and thus currently is not efficiently solvable on classical computers. Here, we propose a biomolecular and a quantum algorithm for this problem, where the quantum algorithm provides a quadratic speedup over any classical algorithm. We show that the dominating set problem can be solved in $$O(2^{n/2})$$ O ( 2 n / 2 ) queries by our proposed quantum algorithm, where n is the number of vertices in G. We also demonstrate that our quantum algorithm is the best known procedure to date for this problem. We confirm the correctness of our algorithm by executing it on IBM Quantum’s qasm simulator and the Brooklyn superconducting quantum device. And lastly, we show that molecular solutions obtained from solving the dominating set problem are represented in terms of a unit vector in a finite-dimensional Hilbert space.

13 June 2023 in arXiv
Verified
Preprint
Open access
PDF file
WCWeng-Long Chang
Weng-Long Chang
RWRenata Wong
Renata Wong
WCWen-Yu Chung
Wen-Yu Chung
YCYu-Hao Chen
Yu-Hao Chen
JCJu-Chin Chen
Ju-Chin Chen
Athanasios V. VasilakosAthanasios V. Vasilakos
Athanasios V. Vasilakos
Given an undirected, unweighted graph with $n$ vertices and $m$ edges, the maximum cut problem is to find a partition of the $n$ vertices into disjoint subsets $V_1$ and $V_2$ such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which has potential applications ranging from circuit layout design, statistical physics, computer vision, machine learning and network science to clustering. In this paper, we propose a quantum algorithm to solve the maximum cut problem for any graph $G$ with a quadratic speedup over its classical counterparts, where the temporal and spatial complexities are reduced to, respectively, $O(\sqrt{2^n/r})$ and $O(m^2)$. With respect to oracle-related quantum algorithms for NP-complete problems, we identify our algorithm as optimal. Furthermore, to justify the feasibility of the proposed algorithm, we successfully solve a typical maximum cut problem for a graph with three vertices and two edges by carrying out experiments on IBM's quantum computer.