ABSTRACT
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 V1 and V2 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 biomolecular and a quantum algorithm to solve the maximum cut problem for any graph G. The quantum algorithm is inspired by the biomolecular algorithm and has a quadratic speedup over its classical counterparts, where the temporal and spatial complexities are reduced to, respectively, [Formula: see text] and [Formula: see text]. 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 simulator.
Subject(s)
Algorithms , Quantum Theory , Computational Biology/methods , Computer SimulationABSTRACT
Currently, the majority of industrial metal processing involves the use of taps for cutting. However, existing tap machines require relocation to specialized inspection stations and only assess the condition of the cutting edges for defects. They do not evaluate the quality of the cutting angles and the amount of removed material. Machine vision, a key component of smart manufacturing, is commonly used for visual inspection. Taps are employed for processing various materials. Traditional tap replacement relies on the technician's accumulated empirical experience to determine the service life of the tap. Therefore, we propose the use of visual inspection of the tap's external features to determine whether replacement or regrinding is needed. We examined the bearing surface of the tap and utilized single images to identify the cutting angle, clearance angle, and cone angles. By inspecting the side of the tap, we calculated the wear of each cusp. This inspection process can facilitate the development of a tap life system, allowing for the estimation of the durability and wear of taps and nuts made of different materials. Statistical analysis can be employed to predict the lifespan of taps in production lines. Experimental error is 16 µm. Wear from tapping 60 times is equivalent to 8 s of electric grinding. We have introduced a parameter, thread removal quantity, which has not been proposed by anyone else.
ABSTRACT
In Industry 4.0, automation is a critical requirement for mechanical production. This study proposes a computer vision-based method to capture images of rotating tools and detect defects without the need to stop the machine in question. The study uses frontal lighting to capture images of the rotating tools and employs scale-invariant feature transform (SIFT) to identify features of the tool images. Random sample consensus (RANSAC) is then used to obtain homography information, allowing us to stitch the images together. The modified YOLOv4 algorithm is then applied to the stitched image to detect any surface defects on the tool. The entire tool image is divided into multiple patch images, and each patch image is detected separately. The results show that the modified YOLOv4 algorithm has a recall rate of 98.7% and a precision rate of 97.3%, and the defect detection process takes approximately 7.6 s to complete for each stitched image.
ABSTRACT
In this paper, we propose a bio-molecular algorithm with O( n 2) biological operations, O( 2n-1 ) DNA strands, O( n ) tubes and the longest DNA strand, O( n ), for inferring the value of a bit from the only output satisfying any given condition in an unsorted database with 2n items of n bits. We show that the value of each bit of the outcome is determined by executing our bio-molecular algorithm n times. Then, we show how to view a bio-molecular solution space with 2n-1 DNA strands as an eigenvector and how to find the corresponding unitary operator and eigenvalues for inferring the value of a bit in the output. We also show that using an extension of the quantum phase estimation and quantum counting algorithms computes its unitary operator and eigenvalues from bio-molecular solution space with 2n-1 DNA strands. Next, we demonstrate that the value of each bit of the output solution can be determined by executing the proposed extended quantum algorithms n times. To verify our theorem, we find the maximum-sized clique to a graph with two vertices and one edge and the solution b that satisfies b2 ≡ 1 (mod 15) and using IBM Quantum's backend.
Subject(s)
Algorithms , Computers , DNA/chemistry , Databases, FactualABSTRACT
In this paper, we propose a bio-molecular algorithm with O( n2 + m ) biological operations, O( 2n ) DNA strands, O( n ) tubes and the longest DNA strand, O( n ), for solving the independent-set problem for any graph G with m edges and n vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with m NAND gates, ( m +n × ( n + 1 )) AND gates and (( n × ( n + 1 ))/2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph G with m edges and n vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound Ω ( 2n/2 ) queries and the upper bound O( 2n/2 ) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph G with m edges and n vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of n bits is to determine whether the given 2n real numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is Ω ( 2n×(2/3) ) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to Ω (( 2n/2 )/( [Formula: see text]) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM's quantum computer.
